QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449289#8359. traveldefinieren15 42ms125952kbC++147.6kb2024-06-20 21:33:032024-06-20 21:33:05

Judging History

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

  • [2024-06-20 21:33:05]
  • 评测
  • 测评结果:15
  • 用时:42ms
  • 内存:125952kb
  • [2024-06-20 21:33:03]
  • 提交

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, k, op;

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;
vector<int> son, ans, G[N];
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;
}

void Main() {
	for (int i = 1; i < n; i ++) {
		int u = Read<int>(), v = Read<int>();
		G[u].emplace_back(v), G[v].emplace_back(u);
	}
	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)]);
	{
		int L = 2 * (n - 1), R = 0;
		for (int u = 1; u <= n; u ++) R += dep[u]; R <<= 1;
		if ((k & 1) || k < L || k > R) { Puts("-1"); return; }
		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);
	}
	{
		son.emplace_back(rt);
		sort(son.begin(), son.end(), [&](int x, int y) { return rng[x].size() > rng[y].size(); });
//		for (auto u : son) for (auto _ : rng[u]) cout << u << ": " << '[' << _.fir << ',' << _.sec << ']' << endl;
//		cout << endl;
		assert(son.size() >= 2);
		int p1 = 0, p2 = 1;
		while (p1 < son.size() && p2 < son.size()) {
			int u = son[p1], v = son[p2];
			while (rng[u].size() && rng[v].size()) {
				int l1, r1, l2, r2;
				tie(l1, r1) = rng[u].back(), rng[u].pop_back();
				tie(l2, r2) = rng[v].back(), rng[v].pop_back();
				for (int i = l1; i <= r1; i ++) ans.emplace_back(ord[i]);
				for (int i = l2; i <= r2; i ++) ans.emplace_back(ord[i]);
			}
			if (rng[u].empty()) cmax(p1, p2), p1 ++;
			if (rng[v].empty()) cmax(p2, p1), p2 ++;
		}
		p1 = min(p1, p2);
		if (p1 < son.size() && rng[son[p1]].size()) {
			assert(rng[son[p1]].size() == 1);
			int l, r; tie(l, r) = rng[son[p1]][0];
			for (int i = l; i <= r; i ++) Write(ord[i], ' ');
		}
		for (auto u : ans) Write(u, ' '); Puts("");
	};
	return;
}
void Clear() {
	rt = dfc = 0; while (Q.size()) Q.pop();
	son.clear(), ans.clear();
	for (int i = 1; i <= n; i ++) {
		G[i].clear(), sz[i] = mxp[i] = dfn[i] = ord[i] = dep[i] = 0;
		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 {
vector<int> G[N];

void Main() {
	for (int i = 1; i < n; i ++) {
		int u = Read<int>(), v = Read<int>();
//		G[u].emplace_back(v), G[v].emplace_back(u);
	}
	Puts("-1");
	return;
}
void Clear() {
	
	return;
}
}

void slv() {
	n = Read<int>(), k = Read<int>(), op = Read<int>();
	if (n == 1) { k ? Puts("-1") : Puts("1"); return; }
	if (n == 2) { k == op ? Puts("1 2") : Puts("-1"); return; }
	return op == 1 ? (Solve1::Main(), Solve1::Clear()) : (Solve2::Main(), Solve2::Clear());
}
void clr() {

	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;
}

詳細信息

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 4ms
memory: 51092kb

input:

0

output:


result:

ok Accepted.

Subtask #2:

score: 2
Acceptable Answer

Test #2:

score: 2
Acceptable Answer
time: 8ms
memory: 100300kb

input:

5
9 28 2
8 6
6 3
3 2
9 5
4 1
1 5
5 2
2 7
9 16 2
1 3
7 8
4 2
2 9
9 8
8 6
6 3
3 5
9 12 1
7 5
5 9
9 2
2 8
6 1
1 8
8 4
4 3
9 22 1
8 5
2 4
4 1
1 6
6 9
7 9
9 5
5 3
9 27 1
2 6
4 8
8 1
5 9
9 1
1 7
7 6
6 3

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #3:

score: 2
Acceptable Answer
time: 11ms
memory: 103356kb

input:

5
9 16 2
4 3
3 1
7 6
2 8
8 6
6 1
1 5
9 5
9 12 1
6 7
5 4
4 1
1 3
3 2
2 7
8 7
7 9
9 14 1
1 2
2 3
6 4
8 9
9 3
3 4
5 4
4 7
9 12 1
9 4
4 1
1 5
3 2
2 6
6 5
8 5
5 7
9 9 1
8 7
7 3
3 2
2 9
4 9
9 1
1 6
6 5

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #4:

score: 2
Acceptable Answer
time: 3ms
memory: 100600kb

input:

5
9 13 1
4 7
7 8
8 5
1 9
2 5
3 5
5 9
9 6
9 16 2
7 3
1 5
5 8
8 9
2 3
4 9
9 3
3 6
9 26 1
1 3
3 8
8 9
7 4
2 6
6 9
9 4
4 5
9 25 1
5 3
7 2
2 4
4 9
6 1
1 9
9 3
3 8
9 14 1
3 8
8 5
5 4
7 6
6 4
4 2
2 9
9 1

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #5:

score: 2
Acceptable Answer
time: 11ms
memory: 103472kb

input:

5
9 27 1
8 2
6 9
9 1
4 5
5 1
1 2
2 7
7 3
9 16 2
2 6
6 9
7 8
8 4
1 4
5 4
4 9
9 3
9 30 1
6 7
9 4
4 2
2 5
1 5
5 3
3 7
7 8
9 12 1
4 1
8 6
6 3
2 5
5 1
1 3
3 7
7 9
9 22 1
2 3
7 8
8 1
1 9
9 5
5 3
3 4
6 4

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #6:

score: 2
Acceptable Answer
time: 7ms
memory: 103156kb

input:

5
9 18 2
7 3
3 8
8 4
4 9
9 1
1 5
2 6
5 6
9 26 2
8 3
3 9
9 5
4 2
2 5
6 7
7 5
5 1
9 25 1
1 5
5 9
9 6
2 4
7 6
6 8
8 4
4 3
9 26 2
1 9
9 4
4 6
5 7
3 7
7 6
6 2
2 8
9 26 2
1 4
4 6
6 8
3 9
9 2
5 8
8 7
7 2

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #7:

score: 2
Acceptable Answer
time: 7ms
memory: 102924kb

input:

5
9 13 1
2 4
5 8
8 1
6 9
9 7
7 1
1 4
4 3
9 29 2
3 2
1 8
8 4
4 6
6 7
5 2
2 9
9 7
9 15 2
1 3
3 7
7 2
2 9
4 5
5 9
9 6
6 8
9 31 1
2 9
9 8
8 6
6 5
5 4
7 4
4 1
1 3
9 21 2
7 2
2 5
1 4
3 6
6 5
9 4
4 5
5 8

output:

-1
-1
-1
-1
-1

result:

points 0.50 Partially Correct | type = 2

Test #8:

score: 4
Accepted
time: 10ms
memory: 55068kb

input:

5
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2

output:

1
1
1
1
1

result:

ok Accepted.

Subtask #3:

score: 4
Acceptable Answer

Dependency #2:

50%
Acceptable Answer

Test #9:

score: 4
Acceptable Answer
time: 3ms
memory: 103952kb

input:

5
13 37 1
3 12
12 7
4 13
13 11
11 8
8 6
1 2
10 9
9 7
7 5
5 6
6 2
13 42 1
2 4
4 13
13 5
5 7
7 12
8 6
6 9
1 10
10 11
3 9
9 12
12 11
13 15 1
9 2
2 11
12 4
4 5
5 6
6 3
3 11
8 13
13 1
7 11
11 10
10 1
13 48 1
11 3
3 4
12 1
7 5
5 8
8 2
2 1
10 1
1 4
4 6
13 9
9 6
13 68 2
13 4
6 5
2 1
1 9
9 11
11 12
12 7
7 5
...

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #10:

score: 4
Acceptable Answer
time: 11ms
memory: 102932kb

input:

5
13 34 2
2 7
5 11
13 1
1 3
8 9
9 6
6 11
11 3
3 7
7 12
12 4
4 10
13 17 1
2 7
7 11
11 9
10 12
12 4
6 13
13 4
4 8
8 3
3 1
1 9
9 5
13 33 1
7 6
6 1
1 10
10 13
9 4
11 12
12 13
8 13
2 4
4 13
13 3
5 3
13 17 1
8 11
11 13
13 3
3 5
10 2
2 1
1 6
12 7
6 5
5 4
4 9
9 7
13 15 1
5 1
8 3
2 13
13 11
11 6
6 7
7 9
9 1
...

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #11:

score: 8
Accepted
time: 0ms
memory: 103804kb

input:

5
13 24 2
1 5
11 12
12 2
2 10
4 9
9 3
6 13
13 8
8 5
5 10
10 3
3 7
13 28 2
13 5
5 7
7 3
9 6
4 10
8 12
1 12
12 6
6 3
3 2
2 10
10 11
13 50 2
4 13
13 8
8 10
10 1
3 5
12 7
7 1
1 9
9 5
5 2
6 2
11 2
13 64 2
10 3
3 9
9 7
7 11
11 5
5 13
6 2
2 8
4 8
1 13
13 8
8 12
13 52 2
13 12
12 8
8 10
5 6
6 11
9 2
7 2
1 10...

output:

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

result:

ok Accepted.

Test #12:

score: 4
Acceptable Answer
time: 7ms
memory: 103376kb

input:

5
13 34 1
8 11
11 2
2 10
9 6
3 1
4 13
13 7
7 6
6 12
12 1
1 10
10 5
13 31 1
11 1
1 9
9 5
6 7
7 2
13 4
4 2
2 10
10 12
12 8
8 5
5 3
13 28 2
2 8
8 9
9 6
6 7
4 13
13 11
11 7
7 5
5 1
12 1
1 3
3 10
13 49 1
11 4
4 1
1 8
8 12
12 3
3 7
6 2
13 7
7 5
2 10
10 9
9 5
13 62 1
12 9
9 5
5 6
6 1
1 4
4 2
2 3
8 11
7 10
...

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #13:

score: 4
Acceptable Answer
time: 7ms
memory: 103908kb

input:

5
13 59 1
10 9
3 8
8 7
7 6
6 12
4 1
13 5
5 12
12 2
2 9
9 1
1 11
13 30 2
9 5
2 1
1 3
3 12
12 8
8 7
7 6
11 10
10 5
5 6
4 6
13 6
13 54 1
11 13
13 12
12 10
9 3
3 5
4 2
6 10
10 7
7 5
5 2
1 2
2 8
13 24 2
2 11
5 12
12 4
8 3
3 6
6 7
7 1
10 9
9 4
4 1
1 11
11 13
13 56 2
3 2
2 8
4 9
9 1
1 5
7 10
10 5
5 11
11 8...

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #14:

score: 4
Acceptable Answer
time: 4ms
memory: 100268kb

input:

5
13 21 2
1 11
11 10
12 6
6 8
8 2
2 4
4 7
9 5
5 3
13 10
10 3
3 7
13 34 1
11 4
4 12
2 13
13 8
8 5
10 6
7 1
3 6
6 12
12 9
1 5
5 9
13 137 2
7 9
13 12
12 4
4 5
5 10
10 11
11 9
9 8
2 1
8 3
3 1
6 1
13 13 1
13 12
12 2
2 8
8 9
9 3
3 10
1 10
10 6
7 5
5 6
6 11
11 4
13 25 2
6 9
4 12
12 5
5 1
1 3
7 13
13 9
9 8
...

output:

-1
-1
-1
-1
-1

result:

points 0.50 Partially Correct | type = 2

Test #15:

score: 8
Accepted
time: 9ms
memory: 54408kb

input:

5
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2

output:

1
1
1
1
1

result:

ok Accepted.

Subtask #4:

score: 7
Acceptable Answer

Test #16:

score: 7
Acceptable Answer
time: 8ms
memory: 100584kb

input:

200
9 38 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 26 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
10 30 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
9 30 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
10 28 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 41 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 44 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10...

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #17:

score: 7
Acceptable Answer
time: 3ms
memory: 103624kb

input:

200
9 8 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 17 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 8 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
10 45 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
9 29 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
10 51 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
9 39 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 16 2
1 2
2 ...

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #18:

score: 14
Accepted
time: 3ms
memory: 53396kb

input:

2000
1 0 2
1 0 1
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2
1 0 1
1 0 1
1 0 2
1 0 1
1 0 1
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2
1 0 2
1 0 1
1 0 1
1 0 2
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2
1 0 1
1 0 1
1 0 1
1 0 1
1 0 2
1 0 2
1 0 2
1 0 1
1 0 1
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2
1 0 2
1 0 1
1 0 1
1 0 2
1 0 2
1 0 1
1...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok Accepted.

Test #19:

score: 7
Acceptable Answer
time: 3ms
memory: 100272kb

input:

50
37 420 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 57 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...

output:

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

result:

points 0.50 Partially Correct | type = 2

Test #20:

score: 7
Acceptable Answer
time: 3ms
memory: 103000kb

input:

20
90 206 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
51 52...

output:

-1
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 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 41 57 42 56 43 55 44 54 45 53 46 52 47 50 51 48 49 
-1
45 44 43 42 41...

result:

points 0.50 Partially Correct | type = 2

Test #21:

score: 7
Acceptable Answer
time: 4ms
memory: 100540kb

input:

5
384 396 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
51 52...

output:

-1
187 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 1...

result:

points 0.50 Partially Correct | type = 2

Test #22:

score: 7
Acceptable Answer
time: 11ms
memory: 102820kb

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 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 50 49 48 47 46 45 44 43 42 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 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 ...

result:

points 0.50 Partially Correct | type = 2

Test #23:

score: 7
Acceptable Answer
time: 10ms
memory: 54460kb

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:

-1

result:

points 0.50 Partially Correct | type = 2

Test #24:

score: 14
Accepted
time: 4ms
memory: 102464kb

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:

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

result:

ok Accepted.

Test #25:

score: 7
Acceptable Answer
time: 0ms
memory: 54784kb

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:

-1

result:

points 0.50 Partially Correct | type = 2

Test #26:

score: 14
Accepted
time: 7ms
memory: 103948kb

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:

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 304 303 302 301 300 299 298 297 296 295 294 293 292 291 290 289 288 ...

result:

ok Accepted.

Subtask #5:

score: 0
Wrong Answer

Dependency #4:

50%
Acceptable Answer

Test #27:

score: 10
Accepted
time: 14ms
memory: 55036kb

input:

500000
1 0 1
1 0 2
1 0 2
1 0 1
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 1
1 0 1
1 0 1
1 0 1
1 0 2
1 0 2
1 0 2
1 0 1
1 0 2
1 0 2
1 0 1
1 0 1
1 0 2
1 0 1
1 0 2
1 0 2
1 0 2
1 0 1
1 0 1
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 2
1 0 1
1 0 1
1 0 2
1 0 2
1 0 2
1 0 2
1 0 1
1 0 1
1 0 2...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok Accepted.

Test #28:

score: 0
Wrong Answer
time: 42ms
memory: 125952kb

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:

-1
-1
-1
-1
-1

result:

wrong answer Wrong Answer.

Subtask #6:

score: 0
Runtime Error

Dependency #3:

50%
Acceptable Answer

Test #42:

score: 6
Acceptable Answer
time: 0ms
memory: 53988kb

input:

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

output:

-1
-1
-1
-1
-1

result:

points 0.50 Partially Correct | type = 2

Test #43:

score: 12
Accepted
time: 0ms
memory: 103816kb

input:

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

output:

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

result:

ok Accepted.

Test #44:

score: 12
Accepted
time: 0ms
memory: 54096kb

input:

5
1 0 1
1 0 1
1 0 2
1 0 1
1 0 2

output:

1
1
1
1
1

result:

ok Accepted.

Test #45:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #4:

50%
Acceptable Answer

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

50%
Acceptable Answer

Dependency #3:

50%
Acceptable Answer

Dependency #4:

50%
Acceptable Answer

Dependency #5:

0%