QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#452640	#8359. travel	definieren	100 ✓	294ms	213800kb	C++14	9.2kb	2024-06-23 19:34:09	2024-06-23 19:34:09

Judging History

你现在查看的是最新测评结果

[2024-06-23 19:34:09]
评测

测评结果：100
用时：294ms
内存：213800kb

查看

[2024-06-23 19:34:09]
提交

answer

#include <bits/stdc++.h>

#define fir first
#define sec second
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n';
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n';
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args);
#else
#define dbg(x) void();
#define dpi(x, y) void();
#define dbgf(fmt, args...) void();
#endif

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;

bool Mbe;
constexpr int MOD = 998244353;
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> bool cmin(T &a, T b) { return a > b ? a = b, true : false; }

namespace FastIO {
	constexpr int LEN = 1 << 20;
	char in[LEN + 1], out[LEN + 1];
	char *pin = in, *pout = out, *ein = in, *eout = out + LEN;

	char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
	void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
	void Flush() { fwrite(out, 1, pout - out, stdout); pout = out; }

	template<typename T> T Read() {
		T x = 0; int f = 1; char ch = gc();
		while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return x * f;
	}
	template<typename T> void Write(T x, char c) {
		static char stk[40]; int tp = 0;
		if (x < 0) pc('-'), x = ~x + 1;
		do stk[tp++] = x % 10 + 48, x /= 10; while (x);
		while (tp --) pc(stk[tp]); pc(c); return;
	}
	void Read(char *s) {
		char ch = gc();
		while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
			(ch >= '0' && ch <= '9'))) ch = gc();
		while ((ch != EOF) && ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
			(ch >= '0' && ch <= '9'))) *s = ch, s ++, ch = gc();
		*s = '\0'; return;
	}
	void Write(char *s) {
		while (*s != '\0') pc(*s), s ++; return;
	}
	void Puts(char *s) {
		Write(s), pc('\n'); return;
	}
}

#define getchar FastIO::gc
#define putchar FastIO::pc
#define Flush FastIO::Flush
#define Read FastIO::Read
#define Write FastIO::Write
#define Puts FastIO::Puts

constexpr int N = 5e5 + 5, LG = 19;
int n, op; ll k;
vector<int> G[N];

namespace Solve2 {
int rt, sz[N], mxp[N], dfn[N], ord[N], dfc, dep[N], bel[N];
pair<int, int> st[LG][N];
priority_queue<pair<int, int>> Q;
multiset<pair<int, int>> s;
vector<int> son, ans;
vector<pair<int, int>> dis[N], rng[N];
bool mrk[N];

void Get_Root(int u, int fa) {
	sz[u] = 1, mxp[u] = 0;
	for (auto v : G[u]) if (v ^ fa)
		Get_Root(v, u), sz[u] += sz[v], cmax(mxp[u], sz[v]);
	cmax(mxp[u], n - sz[u]), rt = mxp[u] < mxp[rt] ? u : rt;
	return;
}
void Dfs1(int u, int fa, int anc) {
	sz[ord[dfn[u] = ++ dfc] = u] = 1, bel[u] = anc;
	st[0][dfn[u]] = make_pair(dep[u] = dep[fa] + 1, fa);
	for (auto v : G[u]) if (v ^ fa) Dfs1(v, u, anc), sz[u] += sz[v];
	return;
}
pair<int, int> ST_Query(int l, int r) {
	int k = __lg(r - l + 1);
	return min(st[k][l], st[k][r - (1 << k) + 1]);
}
int Get_Lca(int u, int v) {
	if (u == v) return u;
	if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
	return ST_Query(u + 1, v).sec;
}

vector<int> Main(ll k, int o) {
	mxp[0] = n + 1, Get_Root(1, rt = 0);
	sz[rt] = dep[rt] = 0, dfn[rt] = dfc = 1, bel[rt] = rt, ord[1] = rt;
	for (auto u : G[rt]) son.emplace_back(u), Dfs1(u, rt, u), sz[rt] += sz[u];
	for (int i = 1; i < LG; i ++)
		for (int j = 1; j + (1 << i) - 1 <= n; j ++)
			st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	{
		ll L = 2 * (n - 1), R = 0;
		for (int u = 1; u <= n; u ++) R += dep[u]; R <<= 1;
//		cout << L << ' ' << R << endl;
		if ((k & 1) || k < L || k > R) return vector<int>(1, -1);
		k = (R - k) >> 1;
	};
	for (int i = 1; i <= n; i ++) {
		if (bel[ord[i]] != bel[ord[i + 1]]) continue;
		dis[bel[ord[i]]].emplace_back(dep[Get_Lca(ord[i], ord[i + 1])], ord[i]);
	}
	for (auto u : son) if (dis[u].size())
		sort(dis[u].begin(), dis[u].end()), Q.emplace(make_pair(dis[u].size(), u));
//	for (auto u : son) {
//		cout << u << ": ";
//		for (auto dist : dis[u]) cout << dist.fir << ' ';
//		cout << endl;
//	}
	if (k) {
		while (Q.size()) {
			int u = Q.top().sec; Q.pop();
			int dist, v; tie(dist, v) = dis[u].back();
			if (dist < k) k -= dist, dis[u].pop_back(), mrk[v] = true;
			else {
				while (dis[u].back().fir > k) dis[u].pop_back();
				mrk[dis[u].back().sec] = true, k = 0; break;
			}
			if (dis[u].size()) Q.emplace(dis[u].size(), u);
		}
	}
	for (int l = 1, r; l <= n; l = r + 1) {
		r = l;
		while (bel[ord[r + 1]] == bel[ord[l]] && mrk[ord[r]]) r ++;
		rng[bel[ord[l]]].emplace_back(l, r);
	}
	{
		vector<pair<int, int>> ret;
//		for (int i = 1; i <= n; i ++) cout << dfn[i] << ' '; cout << endl;
//		for (auto u : son) for (auto _ : rng[u])
//			cout << u << ": " << '[' << _.fir << ',' << _.sec << ']' << endl;
//		cout << endl;
		for (auto u : son) s.insert({rng[u].size(), u});
		ret.emplace_back(dfn[rt], dfn[rt]);
		if (!o) for (auto u : son) reverse(rng[u].begin(), rng[u].end());
		while (s.size() > 1) {
			int u = (*-- s.end()).sec; s.erase(-- s.end());
			int v = (*-- s.end()).sec; s.erase(-- s.end());
			int l, r; tie(l, r) = rng[u].back(); rng[u].pop_back(); ret.emplace_back(l, r);
			tie(l, r) = rng[v].back(); rng[v].pop_back(); ret.emplace_back(l, r);
			if (rng[u].size()) s.insert({rng[u].size(), u});
			if (rng[v].size()) s.insert({rng[v].size(), v});
		}
		if (s.size()) {
			int u = (*s.begin()).sec, l, r;
//			cout << u << endl;
			tie(l, r) = rng[u].back(); ret.emplace_back(l, r);
		}
//		for (auto _ : ret) cout << _.fir << ' ' << _.sec << endl;
		if (o) {
			for (auto _ : ret)
				for (int i = _.sec; i >= _.fir; i --)
					ans.emplace_back(ord[i]);
		} else {
			for (int i = 2; i < ret.size(); i ++) {
				int l, r; tie(l, r) = ret[i];
				for (int j = l; j <= r; j ++) ans.emplace_back(ord[j]);
			}
			ans.emplace_back(rt);
			int l, r; tie(l, r) = ret[1];
			for (int i = r; i >= l; i --) ans.emplace_back(ord[i]);
		}
	};
	return ans;
}
void Clear() {
	rt = dfc = 0; while (Q.size()) Q.pop();
	son.clear(), s.clear(), ans.clear();
	for (int i = 1; i <= n; i ++) {
		sz[i] = mxp[i] = dfn[i] = ord[i] = dep[i] = 0, G[i].clear();
		bel[i] = 0, mrk[i] = false, dis[i].clear(), rng[i].clear();
		for (int j = 0; j < LG; j ++) st[j][i] = {0, 0};
	}
	return;
}
}

namespace Solve1 {
int dep[N], prio[N];
vector<int> dia, ans;

int Dfs(int u, int fa) {
	dep[u] = dep[fa] + 1; int mx = u, x;
	for (auto v : G[u]) if (v ^ fa)
		x = Dfs(v, u), mx = dep[mx] < dep[x] ? x : mx;
	return mx;
}
int Get_Diameter() {
	int u = Dfs(1, 0), v = Dfs(u, 0);
	function<bool(int, int, int)> Find_Diameter
		= [&](int u, int fa, int goal) {
			dia.emplace_back(u);
			if (u == goal) return true;
			for (auto v : G[u]) {
				if (v == fa) continue;
				if (Find_Diameter(v, u, goal)) return true;
			}
			dia.pop_back(); return false;
		}; Find_Diameter(u, 0, v);
	return dep[v] - 1;
}
void Get_Ans(int u, int fa) {
	ans.emplace_back(u);
	sort(G[u].begin(), G[u].end(),
		[&](int x, int y) { return prio[x] < prio[y]; });
	for (auto v : G[u]) if (v ^ fa) Get_Ans(v, u);
	return;
}

vector<int> Main() {
	{
		ll L = 2 * (n - 1) - Get_Diameter();
//		dbg(L)
		if (k < L) return vector<int>(1, -1);
	};
//	cout << k + 2 - (k & 1) << ' ' << (k & 1) << endl;
	if (k >= 2 * (n - 1)) return Solve2::Main(k + 2 - (k & 1), k & 1);
	k = 2 * (n - 1) - k;
	int u = dia[k];
//	for (auto i : dia) cout << i << ' '; cout << endl;
	for (int i = 0; i < k; i ++) prio[dia[i]] = 1;
	Get_Ans(u, 0); return ans;
}
void Clear() {
	Solve2::Clear(), ans.clear(), dia.clear();
	for (int i = 1; i <= n; i ++) dep[i] = prio[i] = 0;
	return;
}
}

void slv() {
	n = Read<int>(), k = Read<ll>(), op = Read<int>();
	for (int i = 1; i < n; i ++) {
		int u = Read<int>(), v = Read<int>();
		G[u].emplace_back(v), G[v].emplace_back(u);
	}
	if (n == 1) { k ? Puts("-1") : Puts("1"); return; }
	if (n == 2) { k == op ? Puts("1 2") : Puts("-1"); return; }
	auto ans = (op == 1 ? Solve1::Main() : Solve2::Main(k, 1));
	for (auto u : ans) Write(u, ' '); Puts(""); return;
}
void clr() {
	op == 1 ? Solve1::Clear() : Solve2::Clear();
	return;
}

bool Med;
int main() {
#ifdef LOCAL
	freopen("!in.in", "r", stdin);
	freopen("!out.out", "w", stdout);
	fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
//	int T = 1;
	int T = Read<int>();
	while (T --) slv(), clr();
	Flush();
#ifdef LOCAL
	fprintf(stderr, "%d ms\n", (int)clock());
#endif
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2

Accepted

Test #1:

score: 2

Accepted

time: 7ms

memory: 42428kb

input:

output:

result:

ok Accepted.

Subtask #2:

score: 4

Accepted

Test #2:

score: 4

Accepted

time: 4ms

memory: 83488kb

input:

output:

2 4 8 1 9 6 7 5 3 
8 4 2 9 7 5 1 3 6 
8 1 6 4 3 2 9 5 7 
6 1 8 7 4 2 3 9 5 
1 3 5 4 2 9 8 6 7

result:

ok Accepted.

Test #3:

score: 4

Accepted

time: 8ms

memory: 75368kb

input:

output:

1 2 8 7 6 9 5 4 3 
1 4 5 3 2 7 8 9 6 
3 2 1 4 6 5 7 9 8 
1 4 9 5 8 7 6 2 3 
5 6 1 9 4 2 3 7 8

result:

ok Accepted.

Test #4:

score: 4

Accepted

time: 4ms

memory: 77368kb

input:

output:

5 2 3 9 1 6 8 7 4 
9 1 5 8 4 6 2 7 3 
4 3 6 7 1 2 5 9 8 
9 8 7 5 6 2 4 3 1 
5 4 6 7 2 9 1 8 3

result:

ok Accepted.

Test #5:

score: 4

Accepted

time: 7ms

memory: 65104kb

input:

output:

1 3 6 7 4 8 9 5 2 
4 3 2 6 9 7 8 5 1 
2 7 4 6 9 8 1 5 3 
5 2 1 4 3 7 9 6 8 
9 1 2 8 7 4 6 5 3

result:

ok Accepted.

Test #6:

score: 4

Accepted

time: 7ms

memory: 65272kb

input:

output:

9 2 6 5 7 3 8 4 1 
5 8 6 3 4 9 7 2 1 
6 3 1 2 4 5 9 8 7 
6 1 3 9 8 5 7 4 2 
8 1 3 9 4 2 7 6 5

result:

ok Accepted.

Test #7:

score: 4

Accepted

time: 0ms

memory: 65092kb

input:

output:

1 8 5 4 2 3 7 9 6 
-1 
-1 
5 3 2 1 9 8 7 6 4 
-1

result:

ok Accepted.

Test #8:

score: 4

Accepted

time: 4ms

memory: 77376kb

input:

output:

result:

ok Accepted.

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #9:

score: 8

Accepted

time: 0ms

memory: 77284kb

input:

output:

6 4 13 10 9 11 3 12 7 1 8 5 2 
9 7 5 10 6 8 13 1 3 4 2 12 11 
8 13 1 10 11 2 9 7 3 6 5 4 12 
2 3 8 11 5 6 9 12 10 13 7 1 4 
5 10 2 3 1 13 9 4 11 8 12 7 6

result:

ok Accepted.

Test #10:

score: 8

Accepted

time: 4ms

memory: 75368kb

input:

output:

3 8 9 6 10 4 12 5 2 13 11 7 1 
11 7 2 9 5 1 3 8 4 13 6 12 10 
13 2 11 7 6 1 9 5 12 10 8 4 3 
2 10 1 6 5 4 9 7 12 3 13 11 8 
12 4 3 8 10 1 5 9 7 6 11 13 2

result:

ok Accepted.

Test #11:

score: 8

Accepted

time: 0ms

memory: 71148kb

input:

output:

10 6 13 8 1 5 7 4 9 3 11 12 2 
3 1 8 12 9 11 4 10 13 5 7 6 2 
1 4 11 6 13 2 8 3 5 12 10 9 7 
13 10 12 3 4 9 6 7 2 11 8 5 1 
2 3 1 13 5 12 6 8 11 10 9 7 4

result:

ok Accepted.

Test #12:

score: 8

Accepted

time: 8ms

memory: 71128kb

input:

output:

10 2 6 11 8 9 7 13 4 5 3 1 12 
12 3 11 1 9 13 4 6 7 2 5 10 8 
7 2 8 9 10 3 12 1 4 13 11 6 5 
7 6 2 11 4 10 1 8 9 12 13 5 3 
3 1 13 6 10 7 5 11 9 12 8 2 4

result:

ok Accepted.

Test #13:

score: 8

Accepted

time: 10ms

memory: 77260kb

input:

output:

12 11 3 4 8 1 7 10 13 9 6 5 2 
6 11 10 2 1 3 12 8 9 13 7 5 4 
2 10 4 12 3 13 1 11 9 6 8 5 7 
1 13 2 11 8 3 6 7 10 9 5 12 4 
11 7 13 10 12 4 6 9 3 1 2 8 5

result:

ok Accepted.

Test #14:

score: 8

Accepted

time: 11ms

memory: 65116kb

input:

output:

-1 
12 8 13 2 4 11 1 6 10 3 7 9 5 
-1 
-1 
-1

result:

ok Accepted.

Test #15:

score: 8

Accepted

time: 3ms

memory: 65112kb

input:

output:

result:

ok Accepted.

Subtask #4:

score: 14

Accepted

Test #16:

score: 14

Accepted

time: 4ms

memory: 73492kb

input:

output:

4 7 3 8 2 9 1 5 6 
5 1 2 9 8 3 7 6 4 
6 10 9 1 2 3 8 4 7 5 
5 9 8 1 7 2 3 6 4 
6 1 2 3 10 9 4 8 7 5 
6 10 1 2 9 3 8 4 7 5 
5 8 4 3 9 2 10 1 6 7 
6 1 2 3 4 10 9 8 7 5 
4 7 3 2 8 9 1 5 6 
3 2 1 4 5 6 7 8 9 10 
6 1 2 3 10 9 8 4 7 5 
6 1 2 3 4 10 9 8 7 5 
6 10 1 2 9 3 8 4 7 5 
5 1 9 2 8 7 3 6 4 
6 1 2 1...

result:

ok Accepted.

Test #17:

score: 14

Accepted

time: 3ms

memory: 65280kb

input:

output:

1 2 3 4 5 6 7 8 9 
5 1 2 3 9 8 7 6 4 
1 2 3 4 5 6 7 8 9 
-1 
5 9 8 1 7 2 3 6 4 
-1 
-1 
5 9 8 7 6 1 2 3 4 
-1 
-1 
-1 
-1 
-1 
-1 
5 9 1 8 2 7 3 6 4 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
1 2 3 4 5 6 7 8 9 
-1 
-1 
-1 
-1 
-1 
-1 
1 2 3 4 5 6 7 8 9 10 
-1 
1 2 3 4 5 6 7 8 9 
-1 
5 9 8 1 7 2 6 3 4 
-1 ...

result:

ok Accepted.

Test #18:

score: 14

Accepted

time: 4ms

memory: 91736kb

input:

output:

result:

ok Accepted.

Test #19:

score: 14

Accepted

time: 0ms

memory: 87492kb

input:

output:

19 1 2 3 4 5 37 36 35 34 33 6 32 7 31 8 30 9 29 10 28 27 11 26 12 25 13 24 14 23 15 22 16 21 17 20 18 
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 
21 40 39 38 37 36 35 34 33 32 1 2 3 4 5 6 7 8 9 31 10 30 11 29 12 28 13 27 14 26 15 25 16 24 1...

result:

ok Accepted.

Test #20:

score: 14

Accepted

time: 4ms

memory: 89716kb

input:

output:

45 44 48 43 49 42 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 46 47 
49 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15...

result:

ok Accepted.

Test #21:

score: 14

Accepted

time: 0ms

memory: 91804kb

input:

output:

14 13 12 11 10 9 8 7 6 5 4 3 2 1 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok Accepted.

Test #22:

score: 14

Accepted

time: 11ms

memory: 89676kb

input:

5
378 26744 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

190 378 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307 306 305 ...

result:

ok Accepted.

Test #23:

score: 14

Accepted

time: 0ms

memory: 85920kb

input:

1
1934 290581 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

968 1934 1933 1932 1931 1930 1929 1928 1927 1926 1925 1924 1923 1922 1921 1920 1919 1918 1917 1916 1915 1914 1913 1912 1911 1910 1909 1908 1907 1906 1905 1904 1903 1902 1901 1900 1899 1898 1897 1896 1895 1894 1893 1892 1891 1890 1889 1888 1887 1886 1885 1884 1883 1882 1881 1880 1879 1878 1877 1876 1...

result:

ok Accepted.

Test #24:

score: 14

Accepted

time: 3ms

memory: 89764kb

input:

1
1919 3856 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

960 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Accepted.

Test #25:

score: 14

Accepted

time: 8ms

memory: 85948kb

input:

1
1835 1628390 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
...

output:

919 916 920 915 921 914 922 913 923 912 924 911 925 910 926 909 927 908 928 907 929 906 930 905 931 904 932 903 933 902 934 901 935 900 936 899 937 898 938 897 939 896 940 895 941 894 942 893 943 892 944 891 945 890 946 889 947 888 948 887 949 886 950 885 951 884 952 883 953 882 954 881 955 880 956 ...

result:

ok Accepted.

Test #26:

score: 14

Accepted

time: 3ms

memory: 89888kb

input:

1
1854 642226 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

928 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Accepted.

Subtask #5:

score: 10

Accepted

Dependency #4:

100%

Accepted

Test #27:

score: 10

Accepted

time: 28ms

memory: 91028kb

input:

output:

result:

ok Accepted.

Test #28:

score: 10

Accepted

time: 100ms

memory: 122500kb

input:

5
93044 1765038246 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

46523 93044 93043 93042 93041 93040 93039 93038 93037 93036 93035 93034 93033 93032 93031 93030 93029 93028 93027 93026 93025 93024 93023 93022 93021 93020 93019 93018 93017 93016 93015 93014 93013 93012 93011 93010 93009 93008 93007 93006 93005 93004 93003 93002 93001 93000 92999 92998 92997 92996 ...

result:

ok Accepted.

Test #29:

score: 10

Accepted

time: 93ms

memory: 188136kb

input:

1
481849 965190 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

240925 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Accepted.

Test #30:

score: 10

Accepted

time: 99ms

memory: 194952kb

input:

1
494761 38887392602 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
...

output:

247381 494761 494760 494759 494758 494757 494756 494755 494754 494753 494752 494751 494750 494749 494748 494747 494746 494745 494744 494743 494742 494741 494740 494739 494738 494737 494736 494735 494734 494733 494732 494731 494730 494729 494728 494727 494726 494725 494724 494723 494722 494721 494720...

result:

ok Accepted.

Test #31:

score: 10

Accepted

time: 149ms

memory: 213800kb

input:

1
490645 44453587331 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
...

output:

245323 490645 490644 490643 490642 490641 490640 490639 490638 490637 490636 490635 490634 490633 490632 490631 490630 490629 490628 490627 490626 490625 490624 490623 490622 490621 490620 490619 490618 490617 490616 490615 490614 490613 490612 490611 490610 490609 490608 490607 490606 490605 490604...

result:

ok Accepted.

Test #32:

score: 10

Accepted

time: 122ms

memory: 207068kb

input:

1
456012 71620971179 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
...

output:

228007 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Accepted.

Test #33:

score: 10

Accepted

time: 36ms

memory: 90588kb

input:

output:

50 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 
-1 
-1 
-1 
49...

result:

ok Accepted.

Test #34:

score: 10

Accepted

time: 53ms

memory: 93864kb

input:

output:

11 14 10 15 9 16 8 7 17 18 19 20 21 22 23 6 5 4 3 2 1 12 13 
13 1 2 3 24 23 4 22 5 21 6 20 7 19 18 8 17 9 16 10 15 11 14 12 
12 1 2 3 4 23 22 21 20 5 19 6 18 7 17 8 16 9 15 10 14 13 11 
12 11 15 10 16 9 17 8 18 7 19 6 20 5 21 4 22 3 23 24 2 1 13 14 
13 25 24 1 23 2 22 3 4 21 5 20 6 19 7 18 8 17 9 16...

result:

ok Accepted.

Test #35:

score: 10

Accepted

time: 62ms

memory: 94028kb

input:

output:

116 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 1 2 3 4 5 6 7 8 9 10 11 ...

result:

ok Accepted.

Test #36:

score: 10

Accepted

time: 68ms

memory: 96588kb

input:

200
2422 1517004 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

output:

1212 2422 2421 2420 2419 2418 2417 2416 2415 2414 2413 2412 2411 2410 2409 2408 2407 2406 2405 2404 2403 2402 2401 2400 2399 2398 2397 2396 2395 2394 2393 2392 2391 2390 2389 2388 2387 2386 2385 2384 2383 2382 2381 2380 2379 2378 2377 2376 2375 2374 2373 2372 2371 2370 2369 2368 2367 2366 2365 2364 ...

result:

ok Accepted.

Test #37:

score: 10

Accepted

time: 81ms

memory: 100808kb

input:

50
9167 6418302 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

4584 9167 9166 9165 9164 9163 9162 9161 9160 9159 9158 9157 9156 9155 9154 9153 9152 9151 9150 9149 9148 9147 9146 9145 9144 9143 9142 9141 9140 9139 9138 9137 9136 9135 9134 9133 9132 9131 9130 9129 9128 9127 9126 9125 9124 9123 9122 9121 9120 9119 9118 9117 9116 9115 9114 9113 9112 9111 9110 9109 ...

result:

ok Accepted.

Test #38:

score: 10

Accepted

time: 90ms

memory: 107240kb

input:

20
24105 203761007 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

12053 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Accepted.

Test #39:

score: 10

Accepted

time: 79ms

memory: 116788kb

input:

10
48337 97528 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
...

output:

24169 48337 48336 48335 48334 48333 48332 48331 48330 48329 48328 48327 48326 48325 48324 48323 48322 48321 48320 48319 48318 48317 48316 48315 48314 48313 48312 48311 48310 48309 48308 48307 48306 48305 48304 48303 48302 48301 48300 48299 48298 48297 48296 48295 48294 48293 48292 48291 48290 48289 ...

result:

ok Accepted.

Test #40:

score: 10

Accepted

time: 87ms

memory: 116012kb

input:

10
48412 869174248 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

24207 48412 48411 48410 48409 48408 48407 48406 48405 48404 48403 48402 48401 48400 48399 48398 48397 48396 48395 48394 48393 48392 48391 48390 48389 48388 48387 48386 48385 48384 48383 48382 48381 48380 48379 48378 48377 48376 48375 48374 48373 48372 48371 48370 48369 48368 48367 48366 48365 48364 ...

result:

ok Accepted.

Test #41:

score: 10

Accepted

time: 86ms

memory: 132912kb

input:

5
91193 4099928074 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

45597 91193 91192 91191 91190 91189 91188 91187 91186 91185 91184 91183 91182 91181 91180 91179 91178 91177 91176 91175 91174 91173 91172 91171 91170 91169 91168 91167 91166 91165 91164 91163 91162 91161 91160 91159 91158 91157 91156 91155 91154 91153 91152 91151 91150 91149 91148 91147 91146 91145 ...

result:

ok Accepted.

Subtask #6:

score: 12

Accepted

Dependency #3:

100%

Accepted

Test #42:

score: 12

Accepted

time: 3ms

memory: 93624kb

input:

output:

27 26 13 3 6 2 15 7 4 28 20 24 17 18 19 11 9 16 22 21 12 8 1 25 14 23 10 5 
9 6 15 7 27 29 13 3 17 26 28 30 16 8 12 19 20 5 1 11 10 2 24 22 25 21 23 4 18 14 
1 16 14 27 24 4 3 13 25 26 23 22 9 11 17 10 7 20 21 8 18 6 15 19 2 5 12 
19 10 26 29 22 16 30 21 7 25 4 5 2 9 17 11 6 13 14 27 24 12 8 20 18 3...

result:

ok Accepted.

Test #43:

score: 12

Accepted

time: 3ms

memory: 89636kb

input:

output:

-1 
-1 
5 12 24 9 10 8 7 25 19 1 26 28 20 14 21 18 15 3 29 4 27 23 16 17 11 22 6 13 2 
-1 
-1

result:

ok Accepted.

Test #44:

score: 12

Accepted

time: 6ms

memory: 93728kb

input:

output:

result:

ok Accepted.

Test #45:

score: 12

Accepted

time: 0ms

memory: 91640kb

input:

output:

18 16 3 24 22 12 6 25 7 2 14 10 13 9 20 27 8 15 26 4 17 23 21 5 11 1 19 
27 10 8 18 9 7 3 16 14 12 28 17 6 4 1 24 11 29 13 15 20 21 23 2 5 26 19 25 22 
27 8 2 12 10 5 22 23 26 9 11 18 13 20 1 19 17 24 16 4 15 14 7 6 28 25 21 3 
23 16 21 4 11 5 13 26 14 24 15 1 8 20 25 3 2 9 7 6 19 17 12 27 22 18 10 ...

result:

ok Accepted.

Test #46:

score: 12

Accepted

time: 4ms

memory: 91664kb

input:

output:

23 11 15 1 20 9 22 16 24 3 26 27 12 14 2 25 19 5 17 13 4 7 21 18 6 10 8 
14 20 6 22 18 9 7 2 10 3 16 11 24 5 23 1 13 25 12 26 19 4 17 15 27 21 8 
24 1 17 22 26 13 18 10 23 6 15 27 25 9 5 20 19 21 3 28 11 16 14 2 8 12 7 4 
17 25 20 27 26 22 12 21 15 16 19 7 8 3 11 10 5 28 2 9 23 18 6 24 14 1 13 4 
4 ...

result:

ok Accepted.

Test #47:

score: 12

Accepted

time: 4ms

memory: 91900kb

input:

output:

13 2 9 5 4 21 25 11 1 29 12 10 7 26 22 16 23 24 18 8 19 20 30 17 28 15 3 6 27 14 
9 13 23 10 28 12 2 18 22 4 19 8 3 15 25 26 29 14 1 17 20 21 7 24 27 16 11 6 5 
11 24 8 6 4 18 3 12 15 10 22 16 23 25 1 7 26 17 27 20 13 14 28 5 9 21 19 2 
21 13 1 25 26 20 27 24 8 5 3 14 10 17 22 12 9 23 11 6 7 18 2 16...

result:

ok Accepted.

Test #48:

score: 12

Accepted

time: 0ms

memory: 93620kb

input:

output:

12 9 7 22 25 3 18 11 24 23 17 21 19 27 28 1 2 4 16 8 10 5 14 15 20 26 13 6 
2 26 28 21 15 22 14 11 5 3 6 10 19 27 16 9 12 20 8 18 25 1 4 24 23 17 13 7 
28 20 17 3 12 1 25 10 14 18 7 23 13 15 5 2 6 21 8 26 22 27 16 4 11 9 24 19 
29 26 1 10 24 8 22 19 5 16 12 14 6 4 25 3 15 20 21 11 2 18 17 30 27 13 2...

result:

ok Accepted.

Test #49:

score: 12

Accepted

time: 8ms

memory: 93668kb

input:

output:

2 25 14 20 7 17 23 8 6 1 27 13 10 18 19 26 11 15 16 5 21 12 9 28 22 24 4 3 
8 5 16 2 22 28 19 20 18 17 15 23 25 21 10 27 13 24 11 1 9 3 14 12 6 4 26 7 
6 7 9 15 8 5 4 21 10 19 23 22 24 16 1 14 25 18 17 26 2 13 11 3 27 20 12 
22 2 26 25 19 9 28 13 14 15 5 21 10 6 20 23 4 16 8 27 18 11 3 17 29 24 12 7...

result:

ok Accepted.

Test #50:

score: 12

Accepted

time: 8ms

memory: 89604kb

input:

output:

11 18 6 19 8 10 1 15 14 27 12 23 24 5 17 20 21 7 22 3 4 13 26 25 16 9 2 
5 26 27 12 4 19 3 13 18 25 23 9 14 1 20 8 22 2 24 16 11 6 17 21 15 10 7 
13 6 2 26 4 16 21 10 7 18 11 22 14 27 9 25 12 1 20 8 23 15 3 5 24 19 17 
9 7 2 22 3 28 21 13 5 20 1 30 15 14 29 10 12 23 17 24 11 19 26 27 16 6 18 25 8 4 ...

result:

ok Accepted.

Test #51:

score: 12

Accepted

time: 4ms

memory: 91696kb

input:

output:

13 2 25 10 21 24 19 4 6 18 7 16 3 11 5 15 23 17 8 1 20 22 26 27 14 12 9 
23 2 28 13 15 18 16 12 21 29 20 8 7 10 9 22 1 17 27 24 3 11 25 5 19 26 6 14 4 
24 20 7 9 2 26 27 3 21 28 12 23 8 16 10 1 29 22 5 13 17 19 11 6 25 15 4 18 14 
29 20 16 4 6 26 25 12 8 18 17 3 23 13 24 11 22 5 1 9 28 19 2 27 7 15 ...

result:

ok Accepted.

Test #52:

score: 12

Accepted

time: 3ms

memory: 91688kb

input:

output:

24 6 14 7 3 10 18 16 21 5 23 19 13 25 27 15 22 2 26 11 12 4 17 20 9 8 1 
23 24 6 17 8 9 16 5 20 21 30 11 13 1 22 3 25 18 28 26 19 14 27 4 2 10 29 15 7 12 
5 9 18 24 26 14 7 22 13 21 30 17 16 12 4 1 25 28 27 15 6 2 8 29 23 3 11 20 19 10 
18 26 11 1 9 21 27 14 15 23 6 16 17 10 3 7 8 12 19 2 25 24 5 4 ...

result:

ok Accepted.

Subtask #7:

score: 18

Accepted

Dependency #4:

100%

Accepted

Dependency #6:

100%

Accepted

Test #53:

score: 18

Accepted

time: 8ms

memory: 91856kb

input:

output:

result:

ok Accepted.

Test #54:

score: 18

Accepted

time: 6ms

memory: 91912kb

input:

output:

24 349 316 80 168 263 136 300 319 38 59 329 293 200 57 321 369 46 127 28 213 177 338 97 227 22 152 195 40 286 253 18 208 43 164 99 354 249 325 366 101 246 154 203 93 284 137 183 236 92 53 37 289 307 310 32 207 145 229 55 36 191 258 333 60 327 131 180 95 82 113 304 73 334 322 10 85 4 328 238 159 54 1...

result:

ok Accepted.

Test #55:

score: 18

Accepted

time: 6ms

memory: 91824kb

input:

1
1981 59778 1
581 1357
1357 1114
1319 822
822 1185
1143 365
619 708
708 1424
1424 1489
1489 1936
1936 1740
1789 1497
1497 387
387 1272
1272 485
1448 418
418 893
1011 1305
1305 176
1593 915
915 1594
1594 1432
1432 1794
1794 837
17 704
704 1542
1270 802
802 1879
1427 608
608 1723
1723 1288
1288 779
7...

output:

1383 1215 1196 1257 1382 1974 1224 878 28 191 1426 555 1344 245 1303 1744 723 695 767 1931 167 1295 433 1718 368 1875 687 852 1097 1700 1137 1228 1633 1100 1534 906 435 886 1688 287 1738 1199 960 472 1979 1094 1214 1906 224 550 1236 1048 1351 289 1928 790 1184 453 1616 896 1886 507 220 920 869 877 1...

result:

ok Accepted.

Test #56:

score: 18

Accepted

time: 7ms

memory: 91988kb

input:

1
1998 29319 1
93 1888
1888 701
701 643
643 1166
294 975
975 574
574 19
19 1224
1435 1480
72 1942
1707 613
613 1451
1272 769
1683 1050
1372 1242
1242 901
191 230
1702 562
562 883
1086 1964
1964 1852
1852 1955
1955 310
1165 1905
54 557
557 1182
1182 973
973 878
878 1950
1950 551
551 1473
1473 1921
11...

output:

1870 925 946 1040 1385 1788 1402 127 585 634 1656 639 691 897 1784 1923 1144 1301 1778 124 298 1904 731 719 816 1965 216 1855 1683 1050 406 708 1535 1915 1447 1211 934 1659 172 1837 412 397 1399 274 1092 1384 455 1367 633 148 1841 441 1931 744 1255 194 578 952 1803 933 893 1819 1261 1938 1285 1208 1...

result:

ok Accepted.

Test #57:

score: 18

Accepted

time: 8ms

memory: 91756kb

input:

1
1916 61288 2
395 1027
1610 1787
1787 357
189 139
139 675
675 1158
1158 1868
1868 1196
719 1579
1131 810
810 227
227 475
475 1060
1092 1602
1298 760
1390 211
211 1839
1839 99
99 618
618 1754
1754 1682
1682 529
529 1460
1555 1589
1589 152
152 1665
1665 1781
1649 1487
1487 870
870 144
144 934
750 162...

output:

179 1300 1246 636 1889 1143 1508 536 453 263 501 1440 1136 205 417 903 907 240 1871 29 834 796 1201 265 765 549 1315 1616 883 610 46 478 1472 1396 474 1049 1610 519 655 808 1352 189 139 675 1158 1868 1196 1787 195 357 1176 1808 781 881 282 164 661 1393 613 1532 1187 380 551 3 1323 871 1224 708 639 1...

result:

ok Accepted.

Test #58:

score: 18

Accepted

time: 4ms

memory: 89704kb

input:

1
1835 91921 1
792 896
527 544
544 1461
1461 1426
1426 399
1350 1246
1246 496
496 227
227 799
799 546
945 779
779 418
1712 108
944 949
949 279
552 73
1311 1756
749 815
815 838
838 802
802 242
242 149
1482 1459
568 180
180 506
506 1270
758 1417
1417 203
898 178
178 386
386 920
920 467
715 76
76 1111
...

output:

1819 1754 1277 1223 1824 1707 508 1444 989 1727 213 445 1597 1368 1345 811 1706 960 372 289 524 1046 860 305 316 452 36 797 351 681 248 1385 112 340 1099 778 1785 1443 758 743 1417 470 203 1670 1175 728 380 165 1509 1160 620 699 304 32 1415 551 1464 1561 1309 92 926 826 635 686 199 1704 166 240 214 ...

result:

ok Accepted.

Test #59:

score: 18

Accepted

time: 0ms

memory: 93644kb

input:

output:

-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
13 9 36 16 20 11 37 8 2 39 3 12 7 38 23 17 24 33 10 32 34 29 18 19 15 25 30 4 31 27 28 21 35 6 14 5 22 1 26 
34 22 28 5 26 36 12 31 14 1 3 4 10 2 33 17 7 32 35 19 37 9 25 6 11 29 27 18 38 13 24 15 30 16 23 21 20 8 
-1 
1 35 8 31 15 7 28 6 21 26 36 2 24 14 11 27 12 10 ...

result:

ok Accepted.

Test #60:

score: 18

Accepted

time: 4ms

memory: 91860kb

input:

output:

5 6 4 3 2 1 
6 3 1 5 4 2 
3 6 1 2 5 4 
5 4 3 1 6 2 
1 2 5 6 3 4 
6 1 4 3 5 2 
1 5 3 4 6 2 
3 4 5 1 2 6 
3 6 5 1 4 2 
5 6 1 4 3 2 
3 5 6 4 2 1 
3 5 6 1 4 2 
3 6 4 5 2 1 
5 2 3 1 6 4 
1 2 4 5 3 6 
1 5 3 6 4 2 
2 4 6 3 1 5 
2 3 4 6 1 5 
4 6 5 3 2 1 
6 1 4 5 2 3 
2 4 1 5 6 3 
5 1 6 4 3 2 
3 2 6 5 1 4 
3...

result:

ok Accepted.

Test #61:

score: 18

Accepted

time: 8ms

memory: 89840kb

input:

output:

1 15 17 2 5 3 8 6 16 12 9 10 18 13 14 4 7 11 19 
5 13 20 6 8 10 17 16 1 7 11 19 3 2 18 4 15 14 9 12 
15 10 4 11 12 18 1 3 16 9 7 5 19 8 14 17 13 6 2 
5 10 4 2 1 16 3 6 15 20 18 13 14 9 19 7 12 11 17 8 
15 10 14 8 17 3 6 1 2 4 11 5 12 9 13 20 19 16 18 7 
1 8 13 16 6 9 17 11 19 10 14 12 15 7 2 3 18 5 ...

result:

ok Accepted.

Test #62:

score: 18

Accepted

time: 4ms

memory: 93640kb

input:

output:

6 18 7 10 9 12 17 2 14 8 16 11 3 15 5 19 1 13 4 
17 5 12 18 2 6 9 4 13 15 1 10 14 7 11 16 8 3 
16 4 18 10 3 5 13 15 6 12 9 17 8 7 19 14 11 2 1 
18 16 7 2 13 9 4 6 1 8 10 3 17 14 11 12 5 15 
20 4 1 19 14 6 11 7 17 12 10 2 16 15 9 18 5 13 8 3 
12 16 14 4 6 5 13 3 2 19 8 11 7 1 9 18 17 15 10 
8 11 9 16...

result:

ok Accepted.

Test #63:

score: 18

Accepted

time: 4ms

memory: 91708kb

input:

output:

94 90 35 16 91 81 51 5 44 53 78 47 19 99 22 59 52 63 13 93 40 37 26 74 2 92 39 12 84 49 61 15 29 71 50 11 73 23 42 7 56 57 64 32 87 77 9 27 24 65 88 69 67 4 95 82 6 80 28 66 58 89 41 18 72 25 54 21 86 98 34 96 68 48 62 31 55 33 1 45 85 30 3 10 36 76 20 75 83 97 38 14 79 46 70 8 60 43 17 
12 83 86 60...

result:

ok Accepted.

Test #64:

score: 18

Accepted

time: 4ms

memory: 89628kb

input:

output:

86 61 90 48 28 77 26 62 76 41 68 43 72 19 47 14 32 51 35 1 89 81 23 39 40 78 87 67 44 25 31 29 42 64 24 17 57 2 10 38 88 82 52 45 21 59 54 73 20 79 7 58 84 11 56 3 85 12 65 71 74 4 37 69 55 63 22 9 70 15 60 80 5 66 50 6 36 30 8 33 83 34 27 18 49 16 75 46 13 53 
12 55 71 58 15 84 90 16 28 88 11 60 5 ...

result:

ok Accepted.

Test #65:

score: 18

Accepted

time: 8ms

memory: 91640kb

input:

output:

58 12 16 25 72 60 33 13 22 44 51 96 1 81 3 88 7 83 23 87 43 59 74 71 54 77 80 76 26 48 52 49 42 50 27 98 32 28 36 97 5 8 69 61 68 47 55 73 62 18 64 6 37 45 30 95 39 53 34 79 19 84 63 24 9 93 29 75 85 66 31 67 35 46 91 92 86 56 57 11 21 2 17 40 78 14 89 65 38 94 20 4 90 82 70 41 15 10 
19 13 46 73 39...

result:

ok Accepted.

Test #66:

score: 18

Accepted

time: 8ms

memory: 91740kb

input:

output:

349 28 74 346 239 90 91 61 370 66 257 179 186 305 195 120 222 6 282 354 75 343 336 190 164 177 358 110 18 279 335 129 380 165 187 62 93 119 114 178 263 97 329 10 192 312 325 221 246 103 213 320 265 310 290 159 63 235 36 345 71 330 374 258 243 210 234 291 169 359 207 146 1 362 135 377 54 230 172 82 2...

result:

ok Accepted.

Test #67:

score: 18

Accepted

time: 4ms

memory: 89852kb

input:

output:

174 371 24 156 99 219 71 293 8 14 65 348 138 38 115 169 133 102 164 193 362 188 266 206 286 72 131 231 374 324 364 9 296 191 278 297 104 114 237 60 338 225 5 61 31 302 89 113 119 84 15 147 3 36 350 64 177 93 322 369 59 221 58 141 194 44 260 70 243 40 370 27 342 1 176 179 139 26 187 184 195 170 154 3...

result:

ok Accepted.

Subtask #8:

score: 10

Accepted

Dependency #7:

100%

Accepted

Test #68:

score: 10

Accepted

time: 7ms

memory: 95748kb

input:

output:

result:

ok Accepted.

Test #69:

score: 10

Accepted

time: 25ms

memory: 92320kb

input:

20
4739 5853376 2
241 1557
2727 144
828 4540
4356 4276
2664 1248
3140 3044
2673 2465
4472 4588
4088 1582
1402 837
249 2576
4222 2011
4326 3478
618 1837
2221 2758
4294 4571
4420 99
783 4166
2904 2230
2043 3395
4697 394
1658 1677
2315 931
4132 173
2863 4183
1156 2961
3832 4207
4175 2577
3526 2571
3844...

output:

4176 2803 2450 14 3323 1069 326 1371 2266 2998 4524 669 1570 3249 4417 4164 2125 720 2506 1401 4651 3926 443 3553 2418 2487 300 2409 1595 109 3407 3538 4194 3334 4560 26 582 509 4215 4227 2023 3069 3897 3228 498 3186 3781 700 3736 3354 4631 1787 2151 2304 1861 327 4257 501 2245 3603 3174 4406 660 28...

result:

ok Accepted.

Test #70:

score: 10

Accepted

time: 19ms

memory: 100024kb

input:

10
9775 28387496 2
4111 1845
5328 8463
5658 5847
3140 4296
2304 2863
3059 9597
3416 4942
4155 8323
5427 420
4277 6009
6681 2156
2015 6300
3901 7434
3626 7491
34 8881
2933 1589
2493 3247
3049 2124
7966 8151
7298 5798
4005 1543
6558 7955
7205 7231
6962 8747
9115 2347
6678 2313
6313 5913
5718 2087
4601...

output:

6531 8257 6539 453 6342 378 4177 9282 9068 6850 4542 1691 5682 8411 8520 6212 7779 5009 2994 1352 2931 4909 1138 309 9307 2032 7037 2371 5215 6989 9043 9154 4047 5308 4848 3625 1771 1315 6526 4062 865 5077 6239 2375 7118 4777 5388 5944 2984 2260 1409 2944 30 6381 92 157 6912 1935 9674 5532 1539 4297...

result:

ok Accepted.

Test #71:

score: 10

Accepted

time: 27ms

memory: 96168kb

input:

5
18424 102019945 1
6009 5000
688 5707
7377 2483
17135 11887
11730 10212
8202 2298
10379 4241
11435 9713
12686 1606
7194 701
4130 17140
12866 7314
5553 17608
17154 14894
476 15049
8664 31
16244 10749
7130 14423
15077 15440
3494 14841
14846 5537
15852 16565
9158 1139
9750 14771
16068 5101
5313 2422
9...

output:

11725 14030 16651 7883 3782 7847 1881 15937 2937 4927 8445 15766 11379 16278 2335 8692 14546 8782 11064 5618 10893 1933 18203 7644 16536 17143 7435 326 858 16986 159 2786 5610 7363 17019 6918 8966 3625 295 13172 12573 17523 18217 4970 12619 7123 6517 13135 5609 6679 1530 16012 18390 15970 11761 8932...

result:

ok Accepted.

Test #72:

score: 10

Accepted

time: 28ms

memory: 102204kb

input:

3
31442 1897522 2
227 18045
19811 21817
17841 21143
23712 9546
31355 10107
2019 12690
10655 15526
21289 27919
21190 18604
762 28189
31092 22046
941 7045
25679 6271
341 5776
16779 28120
396 3989
18232 11559
24181 31300
6960 8713
12363 9404
18439 27196
16813 9762
10651 332
3494 20107
13995 26937
2428 ...

output:

23689 14731 12607 25436 18849 25439 20063 6 17472 25605 3092 19301 14422 14517 14602 3258 3854 2145 1365 12414 3659 1134 30577 15541 21856 31107 11829 2781 11881 10205 14873 15693 13385 3641 22390 25708 6050 26049 18371 27471 3084 22269 29983 4324 26668 14889 10096 2444 4643 12991 18512 11771 903 26...

result:

ok Accepted.

Test #73:

score: 10

Accepted

time: 45ms

memory: 101968kb

input:

3
32308 277196163 1
28236 28059
13478 9068
28454 28849
16817 246
11618 9818
28123 4662
20902 9080
13907 9158
5441 10539
27228 25652
13268 4496
13075 15781
9747 15408
24294 13278
29091 28311
3433 30055
20111 22336
24462 24005
16412 2106
17953 18082
11530 16617
17947 4128
2459 26569
9247 18592
19713 1...

output:

18397 15546 11 25825 29978 3755 15777 20900 18737 21067 25770 17862 28249 31928 10798 5876 19990 239 10454 16761 18538 28735 24006 17517 7505 13599 6215 11787 8531 16039 21788 16015 30048 5824 18328 29934 4408 20630 24209 28660 21961 15397 10591 7733 13759 21263 17307 6071 7270 28163 15037 6659 1713...

result:

ok Accepted.

Test #74:

score: 10

Accepted

time: 8ms

memory: 94084kb

input:

233
427 58203 1
279 292
169 156
224 109
215 332
268 84
335 383
381 6
166 228
261 252
47 241
118 197
136 140
31 80
329 149
241 351
387 61
400 208
60 219
187 199
116 365
420 186
288 98
427 55
391 305
192 40
88 339
278 308
87 322
221 185
415 360
285 295
422 140
10 218
359 92
15 286
286 33
102 396
246 1...

output:

-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
-1 
298 131 89 169 262 194 66 100 305 353 82 389 376 332 6 316 111 279 250 388 168 124 211 344 24 229 246 282 138 222 181 105 239 107 121 102 257 268 67 183 58 128 223 272 173 119 46 72 371 49 382 65 263 193 184 304 254 351 212 8 161 369 337 291 94 227...

result:

ok Accepted.

Test #75:

score: 10

Accepted

time: 15ms

memory: 93696kb

input:

output:

8 7 2 9 6 1 3 5 4 
9 3 10 1 5 6 7 8 4 2 
7 1 4 10 8 6 2 9 3 5 
3 1 5 8 10 9 7 2 6 4 
1 5 7 9 2 6 8 4 3 
3 8 4 7 1 2 9 6 5 
4 1 5 10 3 6 9 2 8 7 
2 1 7 3 10 4 5 6 9 8 
3 6 2 9 7 8 4 5 1 
7 9 8 5 4 6 1 2 3 
4 7 9 5 3 8 6 2 1 
3 4 5 9 1 7 6 8 10 2 
6 3 5 2 10 8 7 9 4 1 
8 6 2 4 7 1 10 5 9 3 
10 2 1 4 9...

result:

ok Accepted.

Test #76:

score: 10

Accepted

time: 19ms

memory: 91944kb

input:

output:

9 10 18 3 16 19 1 15 13 12 17 4 8 7 20 11 6 2 14 5 
1 4 5 11 3 13 15 14 9 19 12 17 8 2 18 7 6 16 10 
14 15 5 12 13 2 10 7 3 9 6 17 8 11 18 16 4 1 
4 1 9 3 2 13 15 7 11 18 16 20 19 12 14 5 17 10 8 6 
14 18 17 15 9 8 12 13 3 7 2 6 19 16 5 11 10 4 1 
3 5 4 18 7 14 17 9 16 12 15 2 11 13 8 10 6 1 
3 20 4...

result:

ok Accepted.

Test #77:

score: 10

Accepted

time: 16ms

memory: 92580kb

input:

output:

23 36 43 9 45 18 44 46 12 14 47 22 37 28 11 10 31 16 15 30 19 7 26 42 35 2 1 27 34 29 25 41 13 8 39 33 5 17 38 6 4 32 20 40 24 21 3 
10 15 23 45 40 21 35 11 17 31 38 28 39 37 36 7 33 44 24 32 27 25 34 16 26 20 3 41 8 19 22 29 2 18 5 13 43 12 9 6 42 46 4 30 14 1 
9 50 39 2 28 25 27 5 15 32 43 11 44 2...

result:

ok Accepted.

Test #78:

score: 10

Accepted

time: 16ms

memory: 92240kb

input:

output:

2 62 63 5 13 24 77 49 17 14 18 27 28 22 48 97 95 58 35 8 76 98 57 34 69 73 86 99 92 9 30 36 1 52 42 66 85 93 89 53 84 29 7 21 67 39 4 70 20 25 40 33 46 51 45 81 60 56 6 3 82 80 31 16 38 87 94 50 10 100 15 55 90 71 75 68 47 59 12 23 78 44 72 43 74 61 79 96 19 41 64 83 11 88 54 37 91 65 32 26 
4 80 1 ...

result:

ok Accepted.

Test #79:

score: 10

Accepted

time: 21ms

memory: 94368kb

input:

500
181 10132 2
63 62
111 83
175 78
89 149
163 95
54 2
165 55
55 119
162 58
131 86
4 8
41 71
15 47
130 20
10 42
35 141
146 166
14 135
181 176
42 7
68 128
51 116
16 64
160 171
38 21
90 25
168 20
100 50
177 132
65 138
43 147
25 164
115 127
27 22
58 21
7 150
44 144
12 141
124 173
102 109
29 153
32 112
...

output:

140 180 51 84 116 68 45 128 108 60 178 157 9 26 88 39 151 48 59 93 162 70 58 134 38 53 21 27 36 22 73 77 54 125 2 13 181 179 176 120 79 57 87 133 81 19 40 75 91 170 118 31 24 145 23 17 175 167 78 72 168 101 130 155 20 96 67 172 46 115 161 127 104 29 80 153 159 160 66 171 124 65 173 138 92 143 100 10...

result:

ok Accepted.

Test #80:

score: 10

Accepted

time: 19ms

memory: 95008kb

input:

200
471 12114 2
415 145
297 397
304 440
14 104
181 443
273 49
105 78
84 2
212 53
432 390
394 451
468 286
127 263
113 238
171 196
59 117
392 349
215 94
356 442
344 338
192 86
66 257
241 450
306 26
272 142
161 384
58 196
218 463
93 23
312 372
54 308
308 68
452 345
51 247
418 76
122 8
198 139
424 108
5...

output:

382 402 446 331 222 361 389 311 204 85 437 132 227 414 365 35 406 109 309 285 357 135 404 231 326 199 115 330 418 76 12 412 452 345 431 54 308 68 153 347 59 117 329 468 286 250 321 317 456 173 31 292 40 261 398 305 469 192 86 128 378 214 461 175 146 278 93 23 111 210 335 110 433 388 246 157 303 258 ...

result:

ok Accepted.

Test #81:

score: 10

Accepted

time: 23ms

memory: 93924kb

input:

100
975 217172 2
649 311
744 359
221 637
308 496
259 838
859 382
738 637
17 87
454 452
546 664
703 942
867 284
754 964
12 467
114 932
36 393
390 469
42 328
115 480
462 329
39 8
233 588
86 130
325 316
872 258
341 967
967 162
941 288
687 871
258 356
321 468
581 476
31 813
133 538
635 824
331 377
71 50...

output:

878 908 441 713 72 278 373 375 493 772 733 779 800 47 876 568 642 339 789 675 926 560 103 320 77 545 829 536 301 184 870 898 133 538 246 195 443 763 714 658 782 150 388 741 923 854 67 965 617 333 804 291 343 934 969 263 438 591 440 389 243 415 899 369 57 540 638 506 473 240 352 244 398 117 666 828 7...

result:

ok Accepted.

Test #82:

score: 10

Accepted

time: 20ms

memory: 95412kb

input:

50
1867 423383 1
1402 1596
1768 1660
84 1611
368 1781
53 1341
996 1046
806 1866
1460 742
1359 1004
1863 605
489 250
388 1318
135 845
392 346
1257 855
654 77
490 640
1808 1148
384 614
1495 275
1196 1236
827 75
75 1712
254 726
1436 1432
1344 1476
728 739
1016 523
523 1837
381 1623
1703 1397
59 1827
52...

output:

491 1488 1670 236 1643 1023 80 227 978 194 407 505 944 33 1210 1052 1463 450 151 371 642 834 352 988 1252 573 752 1842 399 848 838 1366 261 711 441 79 1205 954 1007 1026 1630 1470 1081 948 1414 1055 736 1098 1445 1139 596 217 1348 915 1035 224 1752 1817 8 775 1324 230 59 1827 911 328 747 1775 278 10...

result:

ok Accepted.

Subtask #9:

score: 22

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Dependency #8:

100%

Accepted

Test #83:

score: 22

Accepted

time: 33ms

memory: 94624kb

input:

output:

result:

ok Accepted.

Test #84:

score: 22

Accepted

time: 92ms

memory: 102656kb

input:

100
4914 5868584 2
4855 1980
1713 1299
1733 640
3936 2505
1258 1919
2989 2100
1549 1808
3837 534
2254 2130
459 1376
3914 200
2187 692
3465 2689
4501 1594
4516 3783
4095 3045
22 2133
1256 1369
1073 1136
646 3990
4506 3499
2663 3812
3649 3512
3573 2111
2241 2707
1879 2677
4216 2691
2878 1285
4604 4816...

output:

4138 2144 4395 4773 3586 2863 1414 2077 96 3061 684 3367 4657 2946 2690 1584 2206 2956 873 215 1396 2747 3998 167 1988 1753 3468 4480 1639 4732 2322 665 4829 374 2608 755 415 2578 2867 2215 2306 2795 3695 58 639 4232 1421 4446 2839 3355 1712 3342 4251 457 2123 2842 744 2837 763 1191 4210 1905 1303 4...

result:

ok Accepted.

Test #85:

score: 22

Accepted

time: 89ms

memory: 103476kb

input:

50
9264 14343522 2
4127 3748
8726 7859
1654 448
5251 8559
2277 3834
8033 4427
8913 6115
759 3415
671 312
1678 2639
6702 2797
3520 7485
464 1726
2509 6969
3491 6541
1904 4841
443 3242
6363 7280
2589 1882
2697 5015
9186 9026
125 70
2312 5699
5927 4834
4402 4396
7256 8408
2441 5044
1999 3156
564 3901
2...

output:

3703 3490 346 5245 8332 8937 511 4407 8456 2223 7436 6549 6742 7366 6049 3572 4369 7022 873 3969 349 1330 4314 2400 996 7416 5769 5207 2823 3409 9257 1542 8326 3680 5104 949 504 4143 671 312 908 7061 9106 3863 292 475 7143 7556 998 3926 6598 8384 7269 3136 1603 566 5519 5239 4091 4435 5079 2334 373 ...

result:

ok Accepted.

Test #86:

score: 22

Accepted

time: 101ms

memory: 103904kb

input:

50
9392 58225 1
6228 6729
316 3831
4383 827
4783 206
901 8057
8725 8920
6509 5267
2014 6918
7013 8718
699 1492
7298 8293
309 3846
5194 5883
3758 6754
7087 2643
2026 4947
7467 4209
5897 1024
7167 8508
4305 2042
6807 9031
2272 3612
7696 4195
3339 8474
8564 1256
8979 1773
3222 4076
4412 8107
27 3558
23...

output:

8895 6881 8815 652 8144 6295 681 8950 1072 4408 4867 5535 554 5260 8032 7351 9066 6977 236 8674 599 3134 794 2665 3101 134 8350 7959 1491 4974 9146 726 9102 6259 243 3011 8511 6990 7170 233 4987 5975 1867 811 8126 6206 6025 7515 6334 7288 1289 5001 6047 5725 3100 4750 3854 4644 6314 4741 4282 987 83...

result:

ok Accepted.

Test #87:

score: 22

Accepted

time: 122ms

memory: 103736kb

input:

25
19790 20927306 2
4444 6276
14933 10108
6231 5388
15299 4203
17068 12794
10252 8287
6787 4058
2947 7053
16913 8475
5104 4109
10834 9443
11748 12927
8388 16660
4325 9605
16413 2446
16668 323
2038 4364
19597 2386
17857 2971
12045 2107
10345 15034
5324 4685
1910 9248
19068 3915
8777 3401
17337 2365
1...

output:

3593 10064 2359 6953 7815 16319 12369 5582 7715 17133 13825 5796 8880 4158 6712 6486 12833 17884 13115 13800 15017 1198 3482 1533 1786 3338 11416 13533 137 16115 5637 17416 2822 6602 8270 16501 15252 1625 2964 19173 5350 18092 13641 16246 17521 8155 12409 12922 1703 297 5959 10326 1675 10449 7456 17...

result:

ok Accepted.

Test #88:

score: 22

Accepted

time: 118ms

memory: 101952kb

input:

25
19975 93145930 2
12432 1834
1881 14484
15930 10534
10845 7335
8074 9798
361 16500
1801 6929
4437 3207
14447 5118
6677 4193
1052 4088
869 640
15256 8605
8186 18363
15464 3806
5778 17272
9822 14677
5350 15754
1674 18160
1783 8216
15853 14470
14582 12437
2545 812
1606 18202
19624 9375
1895 6171
8629...

output:

12748 13190 8170 11426 18661 2878 15056 11050 16368 18091 12956 5745 16767 9580 14104 8592 13144 3515 3221 19078 15469 11184 13334 12123 6419 10626 10132 7389 9245 14835 17996 2074 14892 16913 3840 5888 8290 1289 5817 1418 19395 6069 15544 18813 11697 13140 16626 12251 9947 2712 8665 9577 9481 3334 ...

result:

ok Accepted.

Test #89:

score: 22

Accepted

time: 164ms

memory: 111068kb

input:

10
47976 591885312 2
5124 43680
2252 9516
19288 8740
28470 38971
44005 16449
35113 31009
7142 23054
26551 47176
10450 26089
21857 23087
41980 36670
42848 35489
10282 16403
5395 30470
15802 45845
17969 7447
34743 7617
34799 20623
34264 26807
33968 43764
29498 27833
40072 29805
28680 33112
22228 26794...

output:

47561 20110 39161 16467 3663 47077 32141 45775 27426 32557 8642 39207 2918 8692 39233 34700 12783 22122 11929 9969 811 12626 33218 47228 5694 33639 18559 3157 38507 33883 44607 13628 29195 3554 4675 27179 34487 28267 6965 11390 47902 28836 43297 4964 39862 18617 25012 33671 18181 18599 43097 14797 2...

result:

ok Accepted.

Test #90:

score: 22

Accepted

time: 136ms

memory: 108652kb

input:

10
45442 215847028 1
18473 30982
44534 41274
2723 45201
13119 6426
38639 43918
31640 2906
32096 15308
1356 8922
22081 4880
45055 5993
13173 20550
16941 19759
16629 2018
19954 43873
13002 18173
11394 28098
41851 25383
5142 31705
27108 15842
35992 22440
32300 24908
6264 14876
8386 39768
27107 20226
11...

output:

4860 36902 23697 43546 10902 8727 17679 6901 35083 31818 16537 32364 21349 10030 11420 5484 12835 37490 22402 44046 6026 17181 32903 41489 29934 33470 1762 5848 35554 2491 36718 38219 30032 30279 24287 2257 42373 45127 30078 6775 20762 18255 36999 12935 2346 14240 13968 38283 21716 7686 11317 44458 ...

result:

ok Accepted.

Test #91:

score: 22

Accepted

time: 172ms

memory: 123188kb

input:

5
98026 412627902 2
48046 18927
13901 28466
35521 5201
80007 11667
80793 96581
55539 20025
5543 85851
55543 21411
29340 34851
29610 60263
18792 84130
32073 75581
78498 30643
1376 11678
50702 79538
3515 33613
58947 90914
32141 54510
97107 57425
16944 15325
26833 50683
53820 39405
4095 9382
40911 6943...

output:

54951 80465 56799 33639 38706 36130 64887 97224 20488 35992 80132 20548 34927 94160 83225 63900 90762 9953 78009 72698 82797 89846 65359 2404 80418 92210 57368 34830 41233 2020 26654 4983 93665 66415 79955 41341 71523 20804 84262 29107 21238 63587 3364 86048 8759 34217 14485 6831 9221 9159 58678 297...

result:

ok Accepted.

Test #92:

score: 22

Accepted

time: 178ms

memory: 124620kb

input:

5
91305 1628174951 1
56198 20850
52916 85909
35476 56437
1834 9115
12192 10250
42982 57176
9593 27306
24150 48020
65107 42644
78643 42705
52340 56849
10078 23282
57269 5876
77632 26605
32767 24018
81204 21219
47096 12948
33055 2485
54922 15109
4406 72601
71077 36886
57706 24314
9215 42336
36145 6145...

output:

9226 64930 1977 72456 56671 67774 43803 67044 80921 11776 50278 5397 76187 56444 12643 57844 34007 41863 611 36845 17259 27677 49093 70436 86534 2722 22589 49031 7589 3519 60120 4640 74289 64778 50813 43047 7480 32523 66875 49883 14309 85841 43673 13591 79210 72307 35870 80968 48091 26683 81144 1510...

result:

ok Accepted.

Test #93:

score: 22

Accepted

time: 250ms

memory: 187668kb

input:

1
472025 16043466085 1
417926 39623
195768 229314
370537 57531
267104 382113
170933 141578
53561 74294
250159 31886
9352 36181
322148 394068
117039 351210
300887 304015
24549 24940
114489 128610
411952 339863
71691 11387
73530 4523
10760 14371
149252 155462
22680 357719
350109 402379
152082 101050
2...

output:

95952 88650 260625 363545 259404 19571 181088 86225 196792 242834 96193 81679 247666 137612 165997 456946 208211 431174 461731 282084 183540 295824 368031 451130 158975 70833 188281 368232 47265 110971 15738 166012 43486 354181 172712 380855 17163 20044 156923 306949 104495 159893 122221 273850 2569...

result:

ok Accepted.

Test #94:

score: 22

Accepted

time: 55ms

memory: 90556kb

input:

output:

6 7 5 8 1 2 4 3 
2 8 7 1 4 5 6 3 
8 7 1 2 5 4 6 3 
3 1 6 8 4 7 5 2 
3 8 1 6 5 4 2 7 
8 7 5 3 2 4 6 1 
7 5 3 8 1 2 4 6 
3 7 5 8 1 6 4 2 
2 5 1 6 4 3 8 7 
4 1 7 2 8 6 5 3 
2 8 6 3 7 4 5 1 
8 3 2 7 5 4 6 1 
8 7 3 4 1 2 5 6 
8 1 5 6 2 7 4 3 
5 4 2 7 6 1 8 3 
5 1 3 2 7 8 6 4 
6 7 5 1 8 3 4 2 
4 8 7 5 6 3...

result:

ok Accepted.

Test #95:

score: 22

Accepted

time: 294ms

memory: 192164kb

input:

1
482724 69862381824 1
137472 24627
53394 136713
29923 24872
183115 104962
360179 53778
95044 16923
208793 216766
343809 82383
389111 122728
267129 163660
381943 86337
191746 130719
179638 171500
16541 49248
9266 60892
245541 12470
324537 105560
368925 467572
480713 67654
10418 410596
140876 300727
...

output:

181682 4466 254546 132617 299458 362351 202943 466268 72760 478091 243418 342377 88290 568 338407 216903 482564 51013 438309 400717 39039 432277 328160 19874 360879 77750 391454 29864 385056 16456 129852 293591 187424 267168 5850 454518 88483 441032 17298 210276 35318 301357 149505 280810 364174 441...

result:

ok Accepted.

Test #96:

score: 22

Accepted

time: 268ms

memory: 187220kb

input:

1
466556 37068012357 1
296077 254374
55895 139417
250053 262476
281210 151748
361746 75307
38308 211
25635 226913
290473 170308
112117 207274
333222 333380
165721 128597
76733 301893
137129 112197
171945 20656
193257 43287
93646 249912
343755 80957
434796 359970
277965 34924
188290 4117
401431 43469...

output:

416033 425954 121755 124432 213729 102046 117387 82100 113653 283096 24718 405238 369841 446389 321632 9998 11020 315997 160390 327298 5827 5225 261248 170652 76043 175117 378629 279132 400301 100512 212304 426124 298771 350543 373949 143876 416652 113829 7671 443893 87107 400474 324496 1168 231032 ...

result:

ok Accepted.

Test #97:

score: 22

Accepted

time: 251ms

memory: 187476kb

input:

1
470507 15553613111 1
116590 375013
25458 460568
274726 423221
185476 26173
129323 115569
393959 379177
186613 320883
413505 47092
298840 72519
445171 170296
28563 18974
198881 343336
153370 1813
428633 372899
188361 262767
97460 411511
23648 449045
388428 367955
10793 398742
305885 3039
441903 422...

output:

257541 134687 283752 424342 101350 422243 378576 54421 444454 440857 146502 365479 213097 338540 234173 225694 367046 461519 355018 179102 292418 228493 58842 330690 412762 56515 168704 77642 414098 188501 371882 378341 429113 361203 78780 17254 177793 318478 195408 111405 366990 420232 89153 131492...

result:

ok Accepted.

Test #98:

score: 22

Accepted

time: 196ms

memory: 175304kb

input:

1
484644 70415722676 2
387061 60091
283751 60069
107460 354884
445876 55307
338664 281406
388782 24215
35572 117625
177669 98530
7682 233035
116725 414416
355609 95819
475062 198221
241991 472832
44124 13983
140233 377622
213795 216775
272564 443204
119914 351907
326597 142211
466195 381175
457028 2...

output:

271472 292069 293952 474645 266355 411109 188944 85999 430211 151898 150674 312184 215152 83233 233668 307874 425462 209149 477176 454326 173286 212138 356448 405233 15740 282065 389433 323753 373698 273970 374624 116049 101990 410234 27545 55409 429551 317826 80834 474774 425056 290775 369167 10010...

result:

ok Accepted.

Test #99:

score: 22

Accepted

time: 201ms

memory: 170636kb

input:

1
480049 66333578702 2
414780 52384
229954 204017
477598 350060
177290 395393
22600 399649
194443 4952
375752 445636
81605 302911
366288 84718
57315 335522
472784 367329
137447 408097
409021 236863
121965 347700
346918 58159
445793 183641
255068 367810
442172 237707
471652 352900
286081 25476
89138 ...

output:

260795 404973 19442 274073 453331 380342 128746 252543 234094 295007 154638 116747 148614 88643 115604 244024 362562 347820 239251 180895 334268 207629 391899 180057 375407 333197 34220 344915 426533 400459 172587 811 170350 364873 6496 453511 280224 289230 45438 262975 335825 298951 472291 131422 1...

result:

ok Accepted.

Test #100:

score: 22

Accepted

time: 49ms

memory: 93700kb

input:

1000
498 181292 1
55 405
423 313
133 192
359 39
367 203
366 42
100 76
358 263
183 445
87 27
114 402
331 371
272 424
394 194
417 268
285 284
328 59
125 495
495 364
201 407
310 18
337 283
213 154
346 229
16 65
341 480
315 252
393 19
7 153
365 86
95 144
287 349
262 470
332 295
424 255
336 491
491 311
6...

output:

-1 
424 228 252 3 349 21 322 176 298 477 415 341 398 170 136 63 310 435 381 359 129 402 282 281 122 80 441 459 61 461 52 172 221 137 445 397 195 327 373 309 315 226 169 455 289 140 264 292 40 259 29 190 329 368 377 396 457 14 313 265 318 142 75 147 364 213 352 363 358 219 285 448 163 233 468 45 272 ...

result:

ok Accepted.

Test #101:

score: 22

Accepted

time: 73ms

memory: 90720kb

input:

output:

19 27 12 34 31 42 15 43 22 5 4 30 45 14 38 35 11 13 33 18 21 24 25 26 16 37 40 20 39 1 2 9 10 29 32 28 7 8 36 3 44 41 17 23 6 
30 46 16 28 22 17 1 9 41 35 2 43 14 39 44 31 11 3 27 29 4 45 36 32 33 26 18 25 6 13 10 12 38 19 34 23 7 15 37 21 8 5 24 40 42 20 
13 14 33 25 42 32 20 8 1 11 48 18 38 31 49 ...

result:

ok Accepted.

Test #102:

score: 22

Accepted

time: 74ms

memory: 91324kb

input:

2000
230 11927 1
198 69
181 202
214 145
16 114
211 199
20 92
100 194
177 145
55 228
228 152
101 138
203 42
137 186
36 77
189 152
152 196
6 22
57 123
123 213
213 27
217 157
187 127
22 172
172 168
224 155
33 144
144 13
167 166
61 209
135 175
48 200
199 124
50 230
161 109
190 226
30 155
86 79
79 183
29...

output:

184 212 46 2 23 140 113 41 24 37 193 117 146 31 72 122 205 88 159 149 141 204 99 179 53 12 173 80 68 5 217 157 110 76 185 25 223 3 134 219 153 131 29 135 206 175 14 108 147 156 158 208 94 16 120 114 182 187 118 127 189 35 55 129 228 210 152 111 196 98 190 11 226 222 30 225 224 160 155 211 195 199 18...

result:

ok Accepted.

Test #103:

score: 22

Accepted

time: 81ms

memory: 94976kb

input:

output:

94 235 345 337 374 349 106 101 386 458 1 460 48 428 30 330 266 33 276 305 322 222 6 69 358 445 362 272 260 398 353 295 294 320 421 182 49 270 93 261 176 145 99 124 224 249 248 142 19 411 275 90 103 110 118 73 332 57 163 229 250 194 454 77 311 202 258 5 267 137 355 149 390 81 319 230 365 357 221 24 3...

result:

ok Accepted.

Test #104:

score: 22

Accepted

time: 84ms

memory: 98180kb

input:

output:

971 422 333 635 803 935 628 251 893 931 20 421 771 905 272 794 643 765 559 701 625 857 143 363 465 769 713 963 48 121 134 43 123 285 608 700 522 130 110 304 415 375 760 490 827 644 137 841 309 630 875 833 223 6 576 260 922 373 504 674 463 408 514 210 155 135 675 924 710 457 510 198 551 325 672 201 6...

result:

ok Accepted.

Test #105:

score: 22

Accepted

time: 83ms

memory: 95272kb

input:

500
962 55094 2
235 718
135 459
342 659
434 460
921 812
495 217
751 340
546 326
439 820
337 780
523 223
658 277
938 947
701 493
809 501
198 895
883 554
293 504
627 939
103 688
297 215
26 828
3 402
273 885
190 172
470 871
465 889
244 698
356 926
878 940
23 961
730 476
906 459
80 479
823 139
881 395
3...

output:

571 99 510 789 942 1 505 125 127 730 476 50 675 16 6 306 629 235 718 302 521 15 431 623 17 304 517 228 189 368 585 817 427 449 103 688 389 287 503 403 641 179 301 626 421 35 374 575 647 584 107 913 583 204 392 640 721 264 169 96 366 954 148 214 276 108 860 553 78 792 865 298 314 440 410 213 664 742 ...

result:

ok Accepted.

Test #106:

score: 22

Accepted

time: 86ms

memory: 101688kb

input:

100
4746 1051132 2
1237 3867
2107 4075
3048 3224
2208 1419
3875 1498
598 1118
4554 3504
1732 1316
1594 1279
3626 2781
2662 3766
3719 4529
4566 3799
178 2964
340 768
2823 3777
217 2269
2504 2945
345 4068
2882 3668
2116 471
2368 3872
606 1614
2884 961
1854 4389
4510 920
3424 2284
3637 2875
1692 2741
1...

output:

1322 711 4333 2848 4167 76 1535 4740 1362 1655 3609 1879 3990 4006 1272 3851 1924 998 2158 3243 811 1329 3764 3740 441 1603 2401 293 1890 2398 1771 746 2434 3635 3718 2477 3427 1230 4662 3533 4589 1575 3684 144 3144 2652 247 4586 2835 3634 3586 447 4605 1289 1839 4362 579 4406 4226 428 2135 3642 421...

result:

ok Accepted.

Test #107:

score: 22

Accepted

time: 88ms

memory: 102116kb

input:

100
4503 2286264 1
1641 2688
3396 2617
2562 833
1305 2310
638 850
2450 2086
1235 1661
4143 1757
3412 3937
1584 12
1159 736
3175 3109
1202 2747
3778 3893
1592 1029
203 982
3709 1326
2540 2325
2707 893
43 2008
2203 2422
1901 3772
559 3365
4355 2942
1770 3316
2864 2218
2544 359
763 4500
3537 2236
376 2...

output:

666 3832 1416 1138 736 2445 1159 652 1819 3197 1788 3896 1897 2732 4100 4308 1663 49 1333 81 745 196 606 1064 1756 4011 3817 2249 754 3855 3534 1494 4064 2010 1956 3913 498 4091 1666 1265 3883 1970 1809 4243 4381 867 3048 3818 4106 3313 2288 3622 3906 3954 724 3353 943 1196 3174 2239 1507 3348 3207 ...

result:

ok Accepted.