CSES - NOI 2019 Open - Results
Submission details
Task:Graph Ordering
Sender:Jatana
Submission time:2019-03-16 22:23:28 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED7
#2ACCEPTED29
#3ACCEPTED18
#4ACCEPTED21
#5ACCEPTED25
Test results
testverdicttimegroup
#1ACCEPTED0.24 s1, 4, 5details
#2ACCEPTED0.23 s1, 5details
#3ACCEPTED0.07 s1, 5details
#4ACCEPTED0.11 s1, 5details
#5ACCEPTED0.12 s1, 5details
#6ACCEPTED0.02 s2, 3, 5details
#7ACCEPTED0.02 s2, 3, 5details
#8ACCEPTED0.02 s2, 3, 4, 5details
#9ACCEPTED0.01 s2, 3, 4, 5details
#10ACCEPTED0.02 s2, 3, 4, 5details
#11ACCEPTED0.02 s2, 3, 5details
#12ACCEPTED0.02 s2, 3, 5details
#13ACCEPTED0.02 s2, 3, 4, 5details
#14ACCEPTED0.03 s2, 3, 4, 5details
#15ACCEPTED0.03 s2, 3, 4, 5details
#16ACCEPTED0.02 s2, 3, 4, 5details
#17ACCEPTED0.02 s2, 3, 4, 5details
#18ACCEPTED0.03 s2, 3, 4, 5details
#19ACCEPTED0.02 s3, 4, 5details
#20ACCEPTED0.02 s3, 4, 5details
#21ACCEPTED0.02 s3, 4, 5details
#22ACCEPTED0.01 s3, 4, 5details
#23ACCEPTED0.02 s3, 5details
#24ACCEPTED0.01 s3, 5details
#25ACCEPTED0.02 s3, 5details
#26ACCEPTED0.02 s3, 5details
#27ACCEPTED0.01 s3, 5details
#28ACCEPTED0.34 s5details
#29ACCEPTED0.35 s5details
#30ACCEPTED0.34 s4, 5details
#31ACCEPTED0.35 s4, 5details
#32ACCEPTED0.35 s4, 5details
#33ACCEPTED0.34 s4, 5details
#34ACCEPTED0.21 s5details
#35ACCEPTED0.20 s5details
#36ACCEPTED0.20 s5details
#37ACCEPTED0.01 s1, 2, 3, 4, 5details
#38ACCEPTED0.01 s2, 3, 5details
#39ACCEPTED0.02 s2, 3, 5details
#40ACCEPTED0.01 s2, 3, 5details
#41ACCEPTED0.02 s1, 2, 3, 5details
#42ACCEPTED0.02 s2, 3, 5details
#43ACCEPTED0.02 s3, 4, 5details
#44ACCEPTED0.02 s3, 4, 5details
#45ACCEPTED0.03 s2, 3, 4, 5details
#46ACCEPTED0.03 s2, 3, 4, 5details
#47ACCEPTED0.02 s2, 3, 5details
#48ACCEPTED0.01 s3, 4, 5details
#49ACCEPTED0.04 s4, 5details

Compiler report

input/code.cpp: In instantiation of 'void fast_print(const std::vector<_Tp>&) [with T = int]':
input/code.cpp:244:12:   required from 'std::ostream& operator,(std::ostream&, const T&) [with T = std::vector<int>; std::ostream = std::basic_ostream<char>]'
input/code.cpp:614:8:   required from here
input/code.cpp:181:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
input/code.cpp: In function 'void fast_scan(int&)':
input/code.cpp:133:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(int &x) { scanf("%d", &x); }
                          ~~~~~^~~~~~~~~~
input/code.cpp: In function 'void fast_scan(long long int&)':
input/code.cpp:134:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(long long &x) { scanf("%lld", &x); }...

Code

/*
                                                                                                     
                                             `-:://:::-                                             
                                           `//:-------:/:`                                          
                                          .+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .o:--...```..---+/`                                        
                                       `/y+o/---....---:+o.                                         
                                   `...````-os+/:---:/+o/--.`                                       
              `-/+++++/:.      `...`       :h+d+oooo+/+-`   ...                                     
            `/++//:::://++-`....`         -.`//````````:`     `..`                                  
           `o+/::------://o/`           `-` -.          -`       `..`                               
 `---.-o/:./o/::-..``..-ЗАПУСКАЕМ      ..  ..            -`        `...       ``..``                
  `....o+:-++/:--.```..-://s.        `-`  .-              -`          `-o: .-//::::/:-`             
          `:s+/:--....-::/+s-`      .-   `-                -`           -///:--------:/:`           
           ./s+//:::::://oo-``..НЕЙРОННУЮ: СЕТЬ:::::::-`РАБОТЯГИ        `+:--........--:/`          
            .:ooo+++++osso-`    `.:-...`/` ./::-------:/:`   -`         :+--..``````.--:+:...-+:-`  
             `.-/+++++/+-.-`    -.   ``:so:/:--.......--:+`  `-```````o+/+--..`````..--:o/-..:s+:.  
                 ```````:``.. `-`     -` `+:--..`````..--/+-.../.`````..-o:--.......---/o.    `     
                        `:  `:-      -.  .o:--..`` ``..--:o`   `-`      `:o+:--------:+o-`          
                         `-`-...    ..   .o/--...```..--:+/`    `-`     `oy/so/////++o/.`           
                          -/`  `-` `- ``+s/o/:---...---:++.      `-`   .-../d://///:-.`             
                `.---..``-..-    .-/..`````-oo+/:::::/+o+-        `-``-`  `-.  ````                 
             `:++++/+++++-  ..``.-/:`      /y-:/++o++/:.`..`       ./.   `-                         
            -++/::::::://+/..:-``:` ..   `-.`  ```.```    `..`   `..`-` `-                          
       ``  -o//:--....-::/++` -.-`   `-`.-`                 `..`..`  `-.-                           
  -----ss+:++/:--.```..-://s.  /.     `::                    `-:.     ./`                           
  `````/:..+o/::-..``.--:/+s. ..-`   `-``-`                 ..` `-`  `-`-`                          
          `-s+/::-----::/+oo---``-` ..    .:-    ```      .-`     .-.-  `-`                         
           `:oo+//::://+os/..:`..-/:`      :y.-:::::::.`.-`        ./-`  `-`                        
            `./+oooooooo+/.`-    .-:...`.. .//:-------://`        `- `..` `:.                       
              ``.-::::-.``-/`  `-` `-  `oo:+:--.......--:/`      `-    `.:--h.``..```               
                          -.-`.-    .-   `+:--..`````..--//`    `-       /s-//::::::::.             
                         -` `/-      ..  .o:--..`` ``..--:o.```.-        `//:--------://`           
                        -` .-`.-`     -.`-o/--...```..--:+/.``-:....``:-.+:--....`...--:+`          
                       ..`-.   `-.   ``:os:o/:---...---:++.  `-     ``///+:-..``````.--:+-````-.`   
              `.:///////.-`      .:-..` -``-+o+/:::::/+o/.  `-         `:+:-..`````..--:o/:--/ys+-  
            `-++///////+o/. ``....`-.    :` `.:++++++/:.`  .-           -o/---......---/o.   `.`    
           `++//:-----::/+o:..`     .-`   :    ```````    .-           `+so+:--------:++-`          
  `````:-``:o/::-..`..--:/+o`         -.  `-             .-          `../../+o+////+o+:.`           
  -----syo/o+/:--.```..-://s.          .-` `-           .-        `...     ``-:////:-``             
       .` `/s//:--....-::/+s.            -. `-`        .-       `..`                                
           .+o+/:::--:://+s/-..`          .::+y  ```  .-     `..`                                   
            ./oo++////+oso-`   `....       :y-+:::::::/`   ...                                      
             `.:+oooooo/-`         `....-. .//:-------:/:-.`                                        
                ``...``                 /+:+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .+/--...```..--:+/`                                        
                                         `-o/:---...---:++.                                         
                                          `-+o+/:---:/+o/.                                          
                                            `.:+oooo+/-.`                                           
                                               ``````                                               
*/

#ifdef aimbot
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <ostream>
#include <istream>
#include <typeinfo>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <limits>
#include <fstream>
#include <array>
#include <list>
#include <bitset>
#include <functional>
#include <random>
#include <cstring>
#include <chrono>

#define random escape__from__random__aetuhoetnuhshe
#define mt make_tuple
#define x first
#define y second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define umap unordered_map
#define uset unordered_set
#define elif else if
#define len(v) ((int)v.size())
#define f(i, n) for (int i = 0; i < (n); i++)
#define rof(i, n) for (int i = ((n) - 1); i >= 0; i--) 
#define apply(v, act) for (auto &x : v) { act; }
#define log(args...) {string s = #args;deque<string> deq;\
string buf = "";int bal = 0;for (char c : s) {\
if (c == '(' || c == '[' || c == '{') {bal++;\
} else if (c == ')' || c == ']' || c == '}') {\
bal--;} else {if (bal == 0) {if (c == ',') {\
deq.pb(buf);buf = "";} else {if (c != ' ') {\
buf += c;}}}}}if (!buf.empty()) {deq.pb(buf);}\
smart_io::precall_print();smart_io::_print(deq, args);}

#define print    \
smart_io::precall_print(); \
cout,

#define scan cin,

#ifdef fast_allocator
const int MAXMEM = 200 * 1000 * 1024;
char _memory[MAXMEM];
size_t _ptr = 0;
void* operator new(size_t _x) { _ptr += _x; assert(_ptr < MAXMEM); return _memory + _ptr - _x; }
void operator delete (void*) noexcept {}
#endif

using namespace std;

char string_in_buffer[(int)260];


void fast_scan(int &x) { scanf("%d", &x); }
void fast_scan(long long &x) { scanf("%lld", &x); }
void fast_scan(unsigned long long &x) { scanf("%llu", &x); }
void fast_scan(double &x) { scanf("%lf", &x); }
void fast_scan(long double &x) { scanf("%Lf", &x); }
void fast_scan(char &x) { 
	scanf("%c", &x); 
	if (x == '\n') {
		fast_scan(x);
	}
}
void fast_scan(string &x) {
	scanf("%s", string_in_buffer);
	x = string(string_in_buffer);
}

template<class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
	fast_scan(p.first);
	fast_scan(p.second);
}

template <class T>
void fast_scan(vector<T> &v) {
	for (auto &x : v) fast_scan(x);
}

void fast_print(const int &x) { printf("%d", x); }
void fast_print(const unsigned int &x) { printf("%u", x); }
void fast_print(const long long &x) { printf("%lld", x); }
void fast_print(const unsigned long long &x) { printf("%llu", x); }
void fast_print(const double &x) { printf("%.15lf", x); }
void fast_print(const long double &x) { printf("%.15Lf", x); }
void fast_print(const char &x) { printf("%c", x); };
void fast_print(const string &x) { printf("%s", x.c_str());}
void fast_print(const char v[]) { fast_print((string)v); }

template<class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
	fast_print(p.first);
	fast_print(' ');
	fast_print(p.second);
}

template <class T>
void fast_print(const vector<T> &v) {
	if (v.empty()) return;
	fast_print(v[0]);
	for (int i = 1; i < v.size(); i++) {
		fast_print(' ');
		fast_print(v[i]);
	}
}

template <class T>
void fast_print(const vector<vector<T>> &v) {
	if (v.empty()) return;
	fast_print(v[0]);
	for (int i = 1; i < v.size(); i++) {
		fast_print('\n');
		fast_print(v[i]);
	}
}

template <class T>
void fast_print(const T &v) {
	for (const auto &x : v) {
		fast_print(x);
		fast_print(' ');
	}
}


using namespace std;


namespace smart_io {
	string print_start = "";
	string sep = " ";
	bool first_print = false;

	void precall_print() {
		fast_print(print_start);
		print_start = "\n";
		first_print = true;
	}

	void _print(deque<string>) {}
	template<class T, class... Args>
	void _print(deque<string> names, T elem, Args... args) {
		if (!first_print) {
			fast_print("\n");
		} else {
			first_print = false;
		}
		fast_print(names.front());
		fast_print(" = ");
		fast_print(elem);
		names.pop_front();
		_print(names, args...);
	}
} //namespace smart_io


template <class T>
ostream &operator,(ostream &os, const T &object) {
	if (!smart_io::first_print) {
		fast_print(smart_io::sep);
	} else {
		smart_io::first_print = false;
	}
	fast_print(object);
	return os;
}

template <class T>
istream &operator,(istream &is, T &object) {
	fast_scan(object);
	return is;
}

namespace random {
	using namespace std::chrono;
	mt19937 rng(duration_cast< milliseconds >(
		system_clock::now().time_since_epoch()
	).count());
	uniform_real_distribution<> prob_dist(0.0, 1.0);
};

namespace typedefs {
	typedef long long ll;
	typedef unsigned long long ull;
	typedef pair<int, int> pii;
	typedef long double ld;
}

namespace numbers_operation {
	template<class T>
	T floor_mod(T a, T b) {
		if (a >= 0 && b >= 0) return a % b;
		if (a <= 0 && b <= 0) return a % b;
		return abs(b) - (abs(a) % abs(b));
	}
}

using namespace numbers_operation;
using namespace typedefs;
using namespace random;

int n;
vector<vector<int>> g;
vector<pii> edges;
vector<int> uptime;
vector<int> tin;
vector<bool> used;
vector<int> buff;
vector<bool> pick;
vector<int> order;

vector<int> at;

int timer = 0;

void init_time(int v) {
	used[v] = true;
	at[timer] = v; 
	tin[v] = uptime[v] = timer++;
	for (int sub : g[v]) {
		if (used[sub]) continue;
		init_time(sub);
	}
}

void check(int v, int _forb) {
	used[v] = true;
	for (int sub : g[v]) {
		if (used[sub]) continue;
		if (sub == _forb) continue;
		check(sub, _forb);
	}
}
bool is_critical_slow(int v) {
	used = vector<bool>(n, false);
	int cnt = 0;
	for (int sub : g[v]) {
		if (used[sub]) continue;
		cnt++;
		check(sub, v);
	}
	return cnt >= 2;
}
vector<bool> crit;
void go(int v, int _p) {
	used[v] = true;
	for (int sub : g[v]) {
		if (sub == _p) continue;
		if (used[sub]) {
			uptime[v] = min(uptime[v], tin[sub]);
		} else {
			go(sub, v);
			uptime[v] = min(uptime[v], uptime[sub]);
			if (uptime[sub] >= tin[v]) {
				crit[v] = true;
			}
		}
	}
}

void update_critical() {
	tin = vector<int>(n, 0);
	uptime = vector<int>(n, 0);
	used = vector<bool>(n, false);
	init_time(0);
	crit = vector<bool>(n, false);
	used = vector<bool>(n, false);
	go(0, -1);
	crit[0] = is_critical_slow(0);
}

int A = -1;

struct Node {
	Node *l = NULL, *r = NULL, *pref = NULL;
	int prior;
	int size = 1;

	Node() {
		prior = rng();
	} 
};

int get_size(Node *node) {
	return node ? node->size : 0;
}

void update(Node *node) {
	node->size = get_size(node->l) + get_size(node->r) + 1;
}

Node *merge(Node *l, Node *r) {
	if (!l) return r;
	if (!r) return l;
	if (l->prior > r->prior) {
		l->r = merge(l->r, r);
		l->r->pref = l;
		update(l);
		return l;
	} else {
		r->l = merge(l, r->l);
		r->l->pref = r;
		update(r);
		return r;
	}
}

pair<Node*, Node*> split(Node *node, int k) {
	if (!node) return mp(node, node);
	if (get_size(node->l) >= k) {
		if (node->l) node->l->pref = NULL;
		auto t = split(node->l, k);
		node->l = NULL;
		update(node);
		return mp(t.x, merge(t.y, node));
	} else {
		if (node->r) node->r->pref = NULL;
		auto t = split(node->r, k - get_size(node->l) - 1);
		node->r = NULL;
		update(node);
		return mp(merge(node, t.x), t.y);
	}
}

int get_id(Node *node) {
	int id = get_size(node->l);
	while (node->pref) {
		if (node->pref->r == node) {
			id += 1 + get_size(node->pref->l);
		}
		node = node->pref;
	}
	return id;
}

Node *cart = NULL;

vector<Node*> pres;

void dfs(int v, int _p, int end) {
	buff.pb(v);
	if (v == end) {
		for (int x : buff) {
			pres[x] = new Node();
			cart = merge(cart, pres[x]);
			pick[x] = true;
		}
	}
	at[timer] = v;
	uptime[v] = tin[v] = timer++;
	used[v] = true;
	for (int sub : g[v]) {
		if (sub == _p) continue;
		if (used[sub]) {
			uptime[v] = min(uptime[v], tin[sub]);
		} else {
			dfs(sub, v, end);
			uptime[v] = min(uptime[v], uptime[sub]);
		}
	}
	buff.pop_back();
}

void echo(int v, int _p) {
	used[v] = true;

	if (!pick[v]) {
		buff.pb(v);
	}

	int B = at[uptime[v]];
	if (!buff.empty() && pick[B] && B != A) {
		// auto itA = find(order.begin(), order.end(), A);
		// auto itB = find(order.begin(), order.end(), B);
		int itA = get_id(pres[A]);
		int itB = get_id(pres[B]);
		if (itA < itB) {
			auto t = split(cart, itA + 1);

			// order.insert(itA + 1, buff.begin(), buff.end());
			for (int x : buff) {
				pres[x] = new Node();
				t.x = merge(t.x, pres[x]);
			}
			cart = merge(t.x, t.y);
		} else {
			reverse(buff.begin(), buff.end());
			// order.insert(itB + 1, buff.begin(), buff.end());
			auto t = split(cart, itB + 1);
			for (int x : buff) {
				pres[x] = new Node();	
				t.x = merge(t.x, pres[x]);
			}
			cart = merge(t.x, t.y);
		}
		for (int x : buff) {
			pick[x] = true;
		}
		buff.clear();
	}

	for (int sub : g[v]) {
		if (sub == _p) continue;
		if (used[sub]) continue;
		if (pick[v]) {
			A = v;
		}
		echo(sub, v);
	}
}

set<int> finded_crit;
void _index(int v) {
	used[v] = true;
	for (int sub : g[v]) {
		if (used[sub]) continue;
		if (crit[sub]) {
			finded_crit.insert(sub);
		} else {
			_index(sub);
		}
	}
}

void init(int _n) {
	n = _n;
	g.resize(n);
	at.resize(2 * n);
	uptime.resize(n);
	tin.resize(n);
	timer = 0;
}

void add_edge(int a, int b) {
	g[a].pb(b);
	g[b].pb(a);
	edges.emplace_back(a, b);
}

vector<int> get_priors() {
	{
		used = vector<bool>(n, false);
		update_critical();
		used = vector<bool>(n, false);
		vector<int> pos;
		f(i, n) {
			if (crit[i]) continue;
			if (!used[i]) {
				if (len(g[i]) == 1) {
					pos.pb(i);
					used[i] = true;
				} else {
					finded_crit.clear();
					_index(i);
					if (len(finded_crit) <= 1) {
						pos.pb(i);
					}
				}
			}
		}
		if (len(pos) <= 1) {
			pos.pb(n - 1);
		}
		if (len(pos) != 2) {
			return {};
		}

		int start = pos[0];
		int end = pos[1];
		shuffle(pos.begin(), pos.end(), rng);

		used = vector<bool>(n, false);
		pick = vector<bool>(n, false);
		pres.resize(n, NULL);
		timer = 0;
		dfs(start, -1, end);
		buff.clear();
		used = vector<bool>(n, false);
		echo(start, -1);
		vector<int> p(n);
		f(i, n) {
			if (pres[i]) {
				p[i] = get_id(pres[i]);
			} else {
				return {};
			}
		}
		vector<int> in(n), out(n);
		for (pii edge : edges) {
			if (p[edge.x] > p[edge.y]) {
				swap(edge.x, edge.y);
			}
			in[edge.y]++;
			out[edge.x]++;
		}
		bool fail = false;
		f(i, n) {
			if (i != start && in[i] == 0) {
				fail = true;
			}
			if (i != end && out[i] == 0) {
				fail = true;
			}
		}
		if (!fail) {
			return p;
		} else {
			return {};
		}
	}
}


signed main() {
	int n, m;
	scan n, m;
	init(n);
	f(i, m) {
		int a, b;
		scan a, b;
		a--;b--;
		add_edge(a, b);
	}
	vector<int> p = get_priors();
	if (p.empty()) {
		print "IMPOSSIBLE";
		return 0;
	}
	vector<int> order(n);
	f(i, n) {
		order[p[i]] = i;
	}
	apply(order, x++);
	print order;
}

Test details

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

input
100000 99999
8326 74462
11810 58064
21677 73087
62986 25005
...

correct output
1 44159 25721 84659 90058 9960...

user output
1 44159 25721 84659 90058 9960...
Truncated

Test 2

Group: 1, 5

Verdict: ACCEPTED

input
100000 99999
28990 31200
86271 56882
61089 18658
52422 57504
...

correct output
68068 86325 91398 75677 51068 ...

user output
68068 86325 91398 75677 51068 ...
Truncated

Test 3

Group: 1, 5

Verdict: ACCEPTED

input
100000 99999
29378 80094
12282 29378
96138 29378
61870 29378
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 4

Group: 1, 5

Verdict: ACCEPTED

input
100000 99999
97935 71091
9181 31715
73649 47675
45394 25464
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 5

Group: 1, 5

Verdict: ACCEPTED

input
100000 99999
2897 55594
11759 89041
56061 8717
69672 73046
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 6

Group: 2, 3, 5

Verdict: ACCEPTED

input
100 200
55 10
33 57
68 39
29 27
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 7

Group: 2, 3, 5

Verdict: ACCEPTED

input
100 175
71 86
100 88
83 92
25 73
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 8

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
100 200
26 58
49 25
66 20
20 85
...

correct output
1 2 86 60 34 92 23 4 44 89 76 ...

user output
1 64 2 86 60 34 92 23 4 76 94 ...
Truncated

Test 9

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
100 195
19 28
63 48
1 57
1 20
...

correct output
12 97 18 74 36 10 78 50 61 95 ...

user output
1 11 30 93 62 46 44 82 83 37 4...
Truncated

Test 10

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
100 193
48 66
15 67
32 14
36 78
...

correct output
1 56 13 32 14 49 75 93 18 6 54...

user output
1 56 13 12 2 39 90 70 89 3 87 ...
Truncated

Test 11

Group: 2, 3, 5

Verdict: ACCEPTED

input
100 195
47 68
57 61
45 17
80 61
...

correct output
57 20 83 41 25 33 60 91 59 7 7...

user output
1 85 22 89 73 58 9 96 80 92 6 ...
Truncated

Test 12

Group: 2, 3, 5

Verdict: ACCEPTED

input
100 185
43 78
76 99
78 39
83 61
...

correct output
78 43 32 88 26 28 64 81 7 72 2...

user output
7 81 64 28 88 32 72 27 50 66 4...
Truncated

Test 13

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
99 132
96 16
18 89
98 50
66 26
...

correct output
1 12 45 71 97 22 35 9 60 27 20...

user output
1 12 45 71 97 22 35 9 60 27 20...
Truncated

Test 14

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
98 144
25 6
30 34
58 25
31 41
...

correct output
32 7 92 1 63 86 87 14 90 17 81...

user output
1 7 92 32 63 86 87 14 90 17 81...
Truncated

Test 15

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
96 145
19 70
72 92
27 72
17 85
...

correct output
1 50 30 4 10 48 42 5 70 19 29 ...

user output
1 50 30 4 10 48 42 70 5 19 29 ...
Truncated

Test 16

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
96 158
79 74
41 70
8 5
73 90
...

correct output
7 59 44 27 1 30 49 28 80 52 15...

user output
1 27 44 59 7 30 49 28 52 80 15...
Truncated

Test 17

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
96 142
95 35
67 89
91 70
48 21
...

correct output
13 20 81 33 1 51 19 69 16 85 6...

user output
1 20 81 33 13 51 19 85 16 69 6...
Truncated

Test 18

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
72 111
70 17
25 3
58 24
52 9
...

correct output
21 59 48 8 1 2 31 10 11 41 4 5...

user output
1 8 48 59 21 2 31 10 11 41 4 5...
Truncated

Test 19

Group: 3, 4, 5

Verdict: ACCEPTED

input
988 1563
402 701
830 801
50 578
8 144
...

correct output
1 136 368 683 447 304 131 53 8...

user output
1 136 368 683 447 304 131 53 8...
Truncated

Test 20

Group: 3, 4, 5

Verdict: ACCEPTED

input
994 1555
171 541
66 915
330 350
494 251
...

correct output
1 164 205 151 951 797 4 654 14...

user output
1 205 164 151 951 797 4 654 91...
Truncated

Test 21

Group: 3, 4, 5

Verdict: ACCEPTED

input
1000 2000
711 947
775 441
691 471
844 28
...

correct output
1 676 731 662 248 31 165 558 8...

user output
1 788 505 817 19 948 933 214 1...
Truncated

Test 22

Group: 3, 4, 5

Verdict: ACCEPTED

input
1000 2000
811 889
873 984
83 52
144 511
...

correct output
60 909 522 568 40 77 181 441 8...

user output
1 499 217 143 175 476 600 67 7...
Truncated

Test 23

Group: 3, 5

Verdict: ACCEPTED

input
1000 1869
625 715
448 714
110 927
432 1000
...

correct output
224 326 221 30 76 475 666 694 ...

user output
16 605 920 565 801 944 798 333...
Truncated

Test 24

Group: 3, 5

Verdict: ACCEPTED

input
1000 1783
709 1
182 768
355 40
786 260
...

correct output
230 6 135 678 346 19 470 960 3...

user output
6 230 135 678 346 19 470 318 9...
Truncated

Test 25

Group: 3, 5

Verdict: ACCEPTED

input
1000 2000
92 876
273 598
287 535
526 972
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 26

Group: 3, 5

Verdict: ACCEPTED

input
1000 1910
789 821
553 740
889 527
488 730
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 27

Group: 3, 5

Verdict: ACCEPTED

input
1000 1608
910 416
503 898
928 14
412 903
...

correct output
140 404 739 563 63 794 623 948...

user output
63 794 563 739 404 140 623 948...
Truncated

Test 28

Group: 5

Verdict: ACCEPTED

input
100000 198666
5659 89691
91040 53375
96642 56177
28768 57001
...

correct output
45598 74078 1039 83702 16344 8...

user output
90 74884 75317 70485 71767 214...
Truncated

Test 29

Group: 5

Verdict: ACCEPTED

input
100000 197194
41636 91770
63018 23827
39207 93713
67765 47715
...

correct output
79054 61855 53279 55546 60860 ...

user output
864 59338 99282 53479 56885 76...
Truncated

Test 30

Group: 4, 5

Verdict: ACCEPTED

input
100000 199985
13674 42886
51349 6858
78502 18751
13628 65936
...

correct output
17857 81664 4369 61462 79754 8...

user output
1 47064 44643 95695 3618 38599...
Truncated

Test 31

Group: 4, 5

Verdict: ACCEPTED

input
100000 200000
27666 33166
7161 81452
73134 30281
5106 29308
...

correct output
76869 5635 23236 12666 61633 8...

user output
1 73905 76869 81955 60796 8232...
Truncated

Test 32

Group: 4, 5

Verdict: ACCEPTED

input
100000 200000
62814 54729
98407 26888
91808 70132
58916 49730
...

correct output
19788 11202 3496 24237 68564 5...

user output
1 75042 96858 87874 52310 1911...
Truncated

Test 33

Group: 4, 5

Verdict: ACCEPTED

input
100000 200000
2299 91653
21125 75544
54029 94067
86513 45051
...

correct output
1 20339 9304 40427 67694 95656...

user output
1 82115 35075 41831 1948 90826...
Truncated

Test 34

Group: 5

Verdict: ACCEPTED

input
100000 200000
34688 93668
78127 18902
55150 33116
273 88797
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 35

Group: 5

Verdict: ACCEPTED

input
100000 200000
21026 14630
5605 59639
25604 78683
55713 70513
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 36

Group: 5

Verdict: ACCEPTED

input
100000 200000
63190 73606
52072 54105
22092 31495
9189 37924
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 37

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
2 1
2 1

correct output
1 2

user output
1 2

Test 38

Group: 2, 3, 5

Verdict: ACCEPTED

input
7 9
1 2
1 3
2 3
1 4
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 39

Group: 2, 3, 5

Verdict: ACCEPTED

input
9 12
1 2
2 3
3 1
4 5
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 40

Group: 2, 3, 5

Verdict: ACCEPTED

input
5 5
4 2
4 3
2 1
3 1
...

correct output
4 2 3 1 5

user output
2 4 3 1 5

Test 41

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
4 3
1 2
3 2
4 2

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 42

Group: 2, 3, 5

Verdict: ACCEPTED

input
17 30
4 1
3 14
6 16
13 6
...

correct output
7 8 11 15 1 2 9 3 14 13 5 10 1...

user output
2 9 3 14 13 5 10 17 12 16 6 4 ...

Test 43

Group: 3, 4, 5

Verdict: ACCEPTED

input
992 1712
377 709
847 640
261 902
761 693
...

correct output
870 1 925 928 950 257 766 520 ...

user output
1 870 925 928 90 366 826 629 1...
Truncated

Test 44

Group: 3, 4, 5

Verdict: ACCEPTED

input
990 1672
305 445
800 155
365 779
824 247
...

correct output
108 461 160 696 895 655 376 21...

user output
1 326 88 160 461 213 376 655 8...
Truncated

Test 45

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
99 169
35 32
97 43
22 62
33 7
...

correct output
19 70 62 22 54 78 25 14 3 81 1...

user output
1 19 70 62 22 3 81 17 54 78 25...
Truncated

Test 46

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
99 164
62 73
19 35
55 92
79 91
...

correct output
21 25 64 90 17 15 89 95 70 33 ...

user output
1 75 38 96 42 16 33 70 95 89 1...
Truncated

Test 47

Group: 2, 3, 5

Verdict: ACCEPTED

input
53 68
7 46
51 14
3 18
8 40
...

correct output
32 30 38 33 27 12 8 20 2 34 45...

user output
1 28 50 37 5 49 51 38 20 2 34 ...
Truncated

Test 48

Group: 3, 4, 5

Verdict: ACCEPTED

input
996 1902
661 201
19 613
895 438
180 32
...

correct output
220 795 198 239 40 164 773 834...

user output
1 929 80 486 54 620 69 834 647...
Truncated

Test 49

Group: 4, 5

Verdict: ACCEPTED

input
6110 11528
3366 4718
3226 2188
5022 1186
3205 5349
...

correct output
1 2527 2211 554 4201 4522 1494...

user output
1 2527 2211 554 3115 5620 2916...
Truncated