QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#753904#9556. The Hanged Manucup-team5657#AC ✓84ms59184kbC++143.7kb2024-11-16 13:50:272024-11-16 13:50:27

Judging History

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

  • [2024-11-16 13:50:27]
  • 评测
  • 测评结果：AC
  • 用时：84ms
  • 内存：59184kb
查看
  • [2024-11-16 13:50:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 5;

struct edge {
	int to, Next;

	edge() {}
	edge(int to, int Next): to(to), Next(Next) {}
} G[N << 1];

int head[N], cnt;

inline void add_edge(int u, int v) {
	G[++cnt] = edge(v, head[u]);
	head[u] = cnt;
}

int T, n, f[N], g[N];

inline void dfs(int fa, int u) {
	f[u] = g[u] = 0;
	int son = 0;
	for (int i = head[u]; i; i = G[i].Next) {
		int v = G[i].to;
		if (v == fa) {
			continue;
		}
		++son;
		dfs(u, v);
		if (g[v]) {
			f[u] = g[u] = 1;
		}
	}
	if (son & 1) {
		g[u] = 1;
	} else {
		f[u] = 1;
	}
}

vector <pair <int, int> > ans;

int t[N];

inline void solve(int fa, int u, int flg) {
	if (flg == 0) {
		int pos = -1;
		for (int i = head[u]; i; i = G[i].Next) {
			int v = G[i].to;
			if (v == fa) {
				continue;
			}
			if (g[v]) {
				pos = v;
				break;
			}
		}
		vector <int> vec;
		if (pos != -1) {
			solve(u, pos, 1);
			for (int i = head[u]; i; i = G[i].Next) {
				int v = G[i].to;
				if (v == fa || v == pos) {
					continue;
				}
				if (f[v]) {
					solve(u, v, 0);
					vec.emplace_back(v);
				} else {
					solve(u, v, 1);
					vec.emplace_back(t[v]);
				}
			}
			if (vec.size() & 1) {
				ans.emplace_back(make_pair(t[pos], vec[0]));
				for (int i = 1; i < (int)vec.size(); i += 2) {
					ans.emplace_back(make_pair(vec[i], vec[i + 1]));
				}
			} else {
				ans.emplace_back(make_pair(t[pos], u));
				for (int i = 0; i < (int)vec.size(); i += 2) {
					ans.emplace_back(make_pair(vec[i], vec[i + 1]));
				}
			}
		} else {
			for (int i = head[u]; i; i = G[i].Next) {
				int v = G[i].to;
				if (v == fa) {
					continue;
				}
				solve(u, v, 0);
				vec.emplace_back(v);
			}
			for (int i = 0; i < (int)vec.size(); i += 2) {
				ans.emplace_back(make_pair(vec[i], vec[i + 1]));
			}
		}
	} else {
		int pos = -1;
		for (int i = head[u]; i; i = G[i].Next) {
			int v = G[i].to;
			if (v == fa) {
				continue;
			}
			if (g[v]) {
				pos = v;
				break;
			}
		}
		vector <int> vec;
		if (pos != -1) {
			solve(u, pos, 1);
			for (int i = head[u]; i; i = G[i].Next) {
				int v = G[i].to;
				if (v == fa || v == pos) {
					continue;
				}
				if (f[v]) {
					solve(u, v, 0);
					vec.emplace_back(v);
				} else {
					solve(u, v, 1);
					vec.emplace_back(t[v]);
				}
			}
			if (vec.size() & 1) {
				ans.emplace_back(make_pair(t[pos], u));
				for (int i = 1; i < (int)vec.size(); i += 2) {
					ans.emplace_back(make_pair(vec[i], vec[i + 1]));
				}
				t[u] = vec[0];
			} else {
				for (int i = 0; i < (int)vec.size(); i += 2) {
					ans.emplace_back(make_pair(vec[i], vec[i + 1]));
				}
				t[u] = t[pos];
			}
		} else {
			for (int i = head[u]; i; i = G[i].Next) {
				int v = G[i].to;
				if (v == fa) {
					continue;
				}
				solve(u, v, 0);
				vec.emplace_back(v);
			}
			for (int i = 1; i < (int)vec.size(); i += 2) {
				ans.emplace_back(make_pair(vec[i], vec[i + 1]));
			}
			t[u] = vec[0];
		}
	}
}

inline void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		head[i] = 0;
	}
	cnt = 0;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs(0, 1);
	if (!f[1]) {
		cout << "-1\n";
		return;
	}
	ans.clear();
	solve(0, 1, 0);
	cout << ans.size() << "\n";
	for (auto p: ans) {
		cout << p.first << " " << p.second << "\n";
	}
}

int main() {
	#ifdef LOCAL
		assert(freopen("test.in", "r", stdin));
		assert(freopen("test.out", "w", stdout));
	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}
Source code, Language: C++14

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9704kb

input:

3
4
1 2
2 3
2 4
7
1 2
1 3
1 4
4 5
4 6
4 7
6
1 2
2 3
2 4
1 5
5 6

output:

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

result:

ok Good Job! (3 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 7932kb

input:

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

output:

-1
-1
-1

result:

ok Good Job! (3 test cases)

Test #3:

score: 0
Accepted
time: 36ms
memory: 7672kb

input:

100000
3
1 3
2 1
3
2 3
1 2
3
2 3
1 3
3
2 1
1 3
3
1 2
2 3
3
1 3
2 3
3
2 1
1 3
3
2 3
1 2
3
2 3
1 3
3
2 1
1 3
3
2 3
1 2
3
1 3
2 3
3
1 3
2 1
3
2 3
1 2
3
2 3
1 3
3
1 3
2 1
3
1 2
2 3
3
1 3
2 3
3
2 1
1 3
3
1 2
2 3
3
1 3
2 3
3
1 3
2 1
3
2 3
1 2
3
1 3
2 3
3
1 3
2 1
3
2 3
1 2
3
1 3
2 3
3
2 1
1 3
3
2 3
1 2
3
2...

output:

1
2 3
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
2 3
1
3 1
1
2 1
1
2 3
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
2 3
1
3 1
1
2 1
1
2 3
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
2 3
1
3 1
1
2 1
1
2 3
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
2 3
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
3 2
1
3 1
1
2 1
1
2 3
1
3 1
...

result:

ok Good Job! (100000 test cases)

Test #4:

score: 0
Accepted
time: 30ms
memory: 7724kb

input:

75000
4
3 1
2 1
1 4
4
3 1
2 4
1 2
4
2 1
1 3
3 4
4
1 4
2 1
3 4
4
2 1
3 2
1 4
4
3 2
2 4
1 2
4
2 3
3 4
1 2
4
3 4
2 4
1 2
4
3 1
1 4
2 3
4
3 2
1 3
2 4
4
2 3
1 3
3 4
4
1 3
3 4
2 4
4
3 1
1 4
2 4
4
3 2
2 4
1 4
4
2 3
3 4
1 4
4
3 4
2 4
1 4
4
1 4
2 1
3 1
4
2 4
3 1
1 2
4
2 1
3 4
1 3
4
2 1
1 4
3 4
4
1 4
2 1
3 2
...

output:

-1
1
4 3
1
4 2
1
3 2
1
3 4
-1
1
4 1
1
3 1
1
2 4
1
4 1
-1
1
2 1
1
2 3
1
3 1
1
2 1
-1
-1
1
4 3
1
4 2
1
3 2
1
3 4
-1
1
4 1
1
3 1
1
2 4
1
4 1
-1
1
2 1
1
2 3
1
3 1
1
2 1
-1
-1
1
4 3
1
4 2
1
3 2
1
3 4
-1
1
4 1
1
3 1
1
2 4
1
4 1
-1
1
2 1
1
2 3
1
3 1
1
2 1
-1
-1
1
4 3
1
4 2
1
3 2
1
3 4
-1
1
4 1
1
3 1
1
2 4
...

result:

ok Good Job! (75000 test cases)

Test #5:

score: 0
Accepted
time: 36ms
memory: 7764kb

input:

60000
5
2 1
3 1
4 1
1 5
5
1 2
4 1
2 5
3 1
5
1 3
3 5
4 1
2 1
5
2 1
4 5
1 4
3 1
5
3 1
1 5
2 1
4 5
5
3 1
4 2
1 5
2 1
5
1 2
3 1
2 5
4 2
5
4 1
1 2
3 5
2 3
5
3 1
2 4
4 5
1 2
5
4 5
3 1
2 5
1 2
5
1 5
2 1
3 1
4 3
5
1 3
4 1
2 5
3 2
5
4 3
2 1
1 3
3 5
5
3 4
1 3
4 5
2 1
5
2 1
1 3
4 5
3 5
5
3 4
4 1
1 5
2 1
5
3 1
...

output:

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

result:

ok Good Job! (60000 test cases)

Test #6:

score: 0
Accepted
time: 34ms
memory: 7700kb

input:

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

output:

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

result:

ok Good Job! (50000 test cases)

Test #7:

score: 0
Accepted
time: 35ms
memory: 7668kb

input:

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

output:

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

result:

ok Good Job! (42857 test cases)

Test #8:

score: 0
Accepted
time: 38ms
memory: 9752kb

input:

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

output:

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

result:

ok Good Job! (37500 test cases)

Test #9:

score: 0
Accepted
time: 21ms
memory: 7668kb

input:

300
1000
815 567
883 63
783 506
485 779
142 248
218 214
617 238
481 567
20 203
119 212
953 179
44 830
427 156
97 916
763 172
484 512
916 21
417 958
408 257
238 634
891 213
90 208
394 56
758 819
435 26
636 718
880 212
458 662
123 212
239 156
548 314
852 436
722 828
271 429
493 27
910 421
354 143
956 ...

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
...

result:

ok Good Job! (300 test cases)

Test #10:

score: 0
Accepted
time: 34ms
memory: 9980kb

input:

3
100000
21854 12448
41900 78683
26279 40303
96957 78925
50096 72644
14704 14585
44195 23551
3290 42026
25017 64658
4593 10713
29129 13530
62892 43675
23793 13329
97502 10091
78766 44620
59301 95815
25781 93162
12231 24059
77637 66545
53889 84545
65596 58277
31337 87701
29049 43837
99301 2408
41562 ...

output:

-1
-1
-1

result:

ok Good Job! (3 test cases)

Test #11:

score: 0
Accepted
time: 42ms
memory: 11828kb

input:

1
300000
264872 86229
63995 164384
180167 260692
169708 168083
149321 50390
177160 60629
178607 170744
176734 60911
231963 17936
49668 90468
205798 261858
7645 12727
240590 1798
8446 139678
32309 208096
226620 119112
204528 63548
110330 250899
219366 144880
258130 23221
203423 40874
45194 78650
1571...

output:

-1

result:

ok Good Job! (1 test case)

Test #12:

score: 0
Accepted
time: 41ms
memory: 9720kb

input:

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

output:

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

result:

ok Good Job! (30000 test cases)

Test #13:

score: 0
Accepted
time: 36ms
memory: 7932kb

input:

3000
99
79 72
72 6
1 90
94 89
31 28
59 89
78 85
73 35
57 45
45 99
38 57
11 70
26 14
92 13
35 52
30 18
61 15
29 86
60 22
5 57
17 84
36 84
70 37
10 86
80 91
34 87
65 8
42 88
87 25
88 43
8 47
33 78
62 47
15 73
83 77
24 33
97 38
23 77
20 34
85 32
55 22
63 10
66 30
39 5
28 62
89 15
37 49
16 75
74 66
47 4...

output:

33
55 60
16 27
22 14
26 58
76 97
67 45
82 69
41 24
11 78
23 83
33 85
36 17
84 74
40 30
59 94
89 61
81 35
51 52
35 29
9 50
63 86
7 29
48 62
80 19
93 3
79 65
77 86
62 8
57 4
47 44
56 43
53 88
95 1
36
42 87
22 66
57 97
53 17
74 14
91 96
27 12
6 37
39 79
80 41
81 72
10 56
72 55
30 61
95 38
55 77
60 51
8...

result:

ok Good Job! (3000 test cases)

Test #14:

score: 0
Accepted
time: 63ms
memory: 10864kb

input:

3
100000
83890 7467
75295 89651
4062 83955
60269 26734
58357 54437
22200 48174
87338 74094
86583 7977
1136 84701
34461 47665
82355 28324
32412 16170
5270 73823
37181 86410
22445 59139
27816 47294
540 79932
73768 41579
14577 92388
31765 75494
49018 24756
57215 90140
86438 22430
3974 15829
59053 22856...

output:

35389
28550 33144
90432 63342
93161 1742
27244 66752
39887 39379
86374 31692
23387 91734
88497 45166
24639 52211
98194 26021
69349 59578
52211 45390
9654 45390
95830 84739
3397 5345
79055 31523
57857 96729
87673 63217
44663 83659
18109 59394
42050 159
59394 44231
26903 88900
86582 27453
86282 53835
...

result:

ok Good Job! (3 test cases)

Test #15:

score: 0
Accepted
time: 79ms
memory: 13992kb

input:

1
300000
30683 45175
202516 82288
209967 151196
160370 148366
36159 83057
277846 18399
58641 259342
220025 290125
299864 69137
276256 59853
163412 98854
211643 219357
45085 203080
17046 259484
175009 201826
220413 253746
280406 235850
107084 114346
6196 164024
149354 242637
8884 201047
102007 121900...

output:

106225
155066 104057
24604 52177
246666 46516
227785 210009
54154 41497
65131 61661
73436 60414
174876 52060
80300 186930
57825 144485
41497 288302
221430 71270
36453 41813
55852 41813
155823 113901
158376 235846
180113 93781
46817 213782
236304 101700
81977 152777
84358 143603
102702 16117
11278 68...

result:

ok Good Job! (1 test case)

Test #16:

score: 0
Accepted
time: 79ms
memory: 59184kb

input:

1
300000
98923 244101
265083 199522
178854 130825
233559 275176
51110 162632
100454 144508
203138 94733
112144 116959
221684 184011
122356 174675
240265 56410
83529 213874
174757 59833
87918 98194
231431 71105
145121 105056
205429 60598
114418 168280
249115 124674
160102 183789
27460 854
72909 12628...

output:

2
250509 246148
253307 246148

result:

ok Good Job! (1 test case)

Test #17:

score: 0
Accepted
time: 74ms
memory: 13784kb

input:

1
300000
51552 258960
174014 1763
298103 122466
80039 102474
90881 123355
37816 182571
209856 199049
68745 246931
231305 147333
256217 77569
277988 49579
174054 154053
74959 60605
281490 278569
131850 7894
138112 208044
207380 67110
1334 204240
117581 152706
90835 142455
54402 68306
264004 244539
99...

output:

106265
200764 284066
275851 83772
224323 271045
29500 126946
57777 34563
227039 230068
288022 242573
230068 98489
251483 272556
38511 17897
255544 201842
45382 100327
253254 208177
92253 25121
294710 271944
111617 100171
221470 190821
162617 176428
158046 138088
133505 138088
253506 45645
18960 2173...

result:

ok Good Job! (1 test case)

Test #18:

score: 0
Accepted
time: 61ms
memory: 10276kb

input:

3
100000
43104 39350
58310 72159
1910 78304
366 33335
3494 5822
948 92660
11882 15212
69203 4346
45739 21275
65867 55409
61694 88089
71479 40349
35887 88786
52148 61962
82180 65178
93823 47701
43116 75915
86963 34539
50583 74229
40562 91601
12139 88394
52559 57679
25481 60170
31207 85832
4201 92027
...

output:

35377
87970 9570
45720 38584
98583 33972
3471 56678
33972 12722
79157 98309
63071 73133
75148 14270
909 85536
29150 83286
38296 13038
80789 44096
14102 21300
5227 81229
75192 54626
37537 97053
25704 71152
73714 86731
66510 97111
1944 88004
28684 72429
12361 70798
1001 44219
40758 51811
91644 13017
7...

result:

ok Good Job! (3 test cases)

Test #19:

score: 0
Accepted
time: 84ms
memory: 57432kb

input:

1
299999
153306 123584
100430 137396
151712 125355
180598 178628
178522 156317
6811 124889
41530 107031
35237 104587
235884 157908
130785 274651
141969 58315
203297 225663
192833 74643
223470 99863
272704 178999
163551 250862
133718 39962
199271 24737
159107 66084
139074 91207
229404 47856
273704 12...

output:

2
211007 43001
141316 43001

result:

ok Good Job! (1 test case)

Test #20:

score: 0
Accepted
time: 30ms
memory: 7676kb

input:

3000
100
9 37
30 16
87 75
66 20
89 79
78 72
48 5
62 100
61 95
69 93
23 86
18 48
32 24
91 43
54 93
92 63
15 7
6 92
67 35
65 89
8 26
21 98
1 65
40 85
36 41
77 39
56 44
69 70
46 67
80 60
94 96
14 36
34 99
84 62
22 74
23 79
46 19
27 51
11 14
18 70
85 8
73 6
97 40
71 83
41 98
61 87
2 90
45 5
20 44
17 81
...

output:

2
2 65
25 65
2
82 51
31 51
2
82 60
48 60
2
95 91
51 91
2
58 90
88 90
2
51 42
31 42
2
14 40
98 40
2
33 10
95 10
2
29 51
41 51
2
22 19
80 19
2
11 94
90 94
1
57 1
2
75 33
7 33
2
25 15
80 15
2
26 65
60 65
2
53 52
14 52
1
63 1
2
17 16
7 16
1
8 1
2
100 36
33 36
1
50 54
2
11 22
57 22
2
30 31
88 31
2
28 31
...

result:

ok Good Job! (3000 test cases)

Test #21:

score: 0
Accepted
time: 77ms
memory: 37696kb

input:

1
299999
123584 153306
137396 100430
114758 125355
180598 13155
156317 178522
124889 6811
41530 27377
104587 35237
157908 235884
130785 44576
141969 129416
225663 203297
120350 74643
20300 99863
295855 178999
198163 250862
133718 148059
24737 199271
66084 159107
91207 139074
229404 89529
273704 1565...

output:

149999
43304 17055
188599 35439
58512 107518
186928 230073
98141 35597
149381 287164
200178 115771
116186 209283
159889 36147
244709 88779
136934 93170
224861 107491
199032 152777
135168 146413
28926 269441
18334 104131
164775 20526
26186 8029
60522 200589
120471 288620
108039 195883
185748 233945
1...

result:

ok Good Job! (1 test case)

Test #22:

score: 0
Accepted
time: 57ms
memory: 10612kb

input:

10
29999
29014 14470
26823 2725
13020 1832
9002 521
22160 26983
2964 2174
20830 22020
19201 4850
19060 10457
23936 2163
22700 29072
28735 4318
15942 8678
10533 9761
8946 29013
12121 555
14303 26560
18146 20485
16984 345
22717 347
21795 27399
20125 489
6200 24303
21419 17994
28274 28769
28326 25399
1...

output:

14999
28453 23907
15770 2920
4578 10326
24984 27593
1186 21879
8661 23588
6245 22099
26588 11850
27247 27395
753 10476
18957 12794
15447 22591
22536 17765
17275 19499
445 16647
25765 27680
16011 16086
28687 13029
2733 22326
1258 8253
18060 8517
14385 19084
1407 3375
19322 10732
12939 26691
14557 289...

result:

ok Good Job! (10 test cases)

Test #23:

score: 0
Accepted
time: 71ms
memory: 14668kb

input:

1
299999
258553 127891
200368 10642
134395 33327
66807 64283
298570 239432
106569 74919
101275 256095
215172 160205
258907 145255
294970 120844
120747 17359
231598 191111
103394 179995
276483 13575
153143 236649
32255 165538
13973 180565
114480 173795
280161 260850
239991 6207
137809 102438
160694 2...

output:

149999
172067 153893
48585 123357
229292 165236
254362 54641
86001 74086
116153 37830
47919 242515
80774 131214
2720 4408
57250 45799
198706 4478
252262 102309
107183 124803
220731 15309
163896 86193
75869 291564
208708 2427
255942 38479
175911 248670
191536 28601
178660 1180
40711 197257
147988 274...

result:

ok Good Job! (1 test case)

Test #24:

score: 0
Accepted
time: 57ms
memory: 8176kb

input:

10
29999
21547 280
5396 29060
21129 24483
1948 5302
5994 20221
12679 20525
23088 2218
24614 17646
9854 7760
23220 29541
9824 25475
9144 8680
17400 22930
3583 13702
14210 16949
4145 4827
4927 15200
5195 13939
23998 23812
20779 22916
19383 23442
29184 11705
12676 19405
4120 11612
24747 1107
25087 1775...

output:

14999
7062 27585
14536 15867
1534 24041
29139 21322
22032 17389
24426 25701
13260 22845
12559 15022
24722 19952
29323 14888
7465 26322
1111 4902
27491 24462
25885 26523
5466 7519
11412 15984
9808 15616
22221 4044
11137 17307
6288 28389
20542 626
12156 14070
9665 29499
11605 1647
26078 4714
12880 233...

result:

ok Good Job! (10 test cases)

Test #25:

score: 0
Accepted
time: 40ms
memory: 7680kb

input:

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

output:

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

result:

ok Good Job! (27000 test cases)

Test #26:

score: 0
Accepted
time: 38ms
memory: 9716kb

input:

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

output:

2
6 1
5 4
1
2 3
4
2 10
7 8
4 1
5 9
6
16 8
11 5
14 7
10 12
17 6
9 1
5
11 8
12 5
3 14
2 7
10 6
4
7 2
10 9
8 5
4 1
7
11 10
4 3
9 16
13 2
12 8
16 14
7 1
5
11 2
9 7
3 5
10 4
12 1
-1
2
4 5
3 1
4
8 3
4 7
6 11
2 9
3
2 10
3 9
5 1
4
7 10
3 11
13 8
6 2
3
10 9
2 3
6 1
1
4 2
2
3 4
2 1
-1
1
3 1
1
2 3
3
5 4
7 3
10...

result:

ok Good Job! (30000 test cases)

Test #27:

score: 0
Accepted
time: 64ms
memory: 12848kb

input:

1
253253
50359 179100
159762 56963
156480 129546
194694 165531
171829 15612
8904 244239
167203 79755
59278 193676
6064 179420
93089 11873
208865 161063
72803 55831
6938 69443
182632 252034
15492 123140
26694 88239
59982 95642
209852 233064
205527 137224
222851 93508
28102 71250
250703 159154
54445 3...

output:

101956
55922 116852
32473 186744
92801 27925
60316 89551
1444 222573
237332 89551
34813 104269
944 222573
1500 136602
178013 86107
123151 229601
249432 41588
215776 75787
253015 177585
223508 227938
113877 239410
132239 227938
111487 187256
192879 54479
47959 207082
54479 28337
165267 188416
53602 2...

result:

ok Good Job! (1 test case)

Test #28:

score: 0
Accepted
time: 48ms
memory: 7684kb

input:

300
1855
1007 450
4 615
1845 844
426 65
1135 79
1020 1386
935 343
936 16
219 1370
1495 131
1409 13
1087 31
63 804
145 1689
1750 1731
694 623
243 626
418 1383
1396 990
1234 385
867 969
779 337
615 732
657 286
1134 1651
269 582
903 1755
478 1384
1360 1060
144 1082
217 1537
185 61
1634 1813
313 876
879...

output:

753
536 168
217 116
1353 290
912 940
825 738
1514 471
835 290
437 1334
738 505
709 605
1518 1256
459 137
403 161
777 137
354 1334
161 914
107 502
380 433
375 283
433 122
984 1637
1519 619
1100 252
1524 1103
703 587
357 1756
753 1130
1368 77
367 430
1747 399
1516 470
1699 979
1083 399
38 1851
435 178...

result:

ok Good Job! (300 test cases)

Test #29:

score: 0
Accepted
time: 59ms
memory: 14312kb

input:

1
297722
2542 280838
47066 211579
45334 161254
161254 3387
161254 81700
286925 161254
188708 161254
163323 239454
177641 142518
161254 141588
161254 289112
161254 132883
161254 264103
161254 7898
131553 35341
274424 85972
161254 111454
161254 245526
195088 87188
83391 252892
74347 144981
248942 2949...

output:

109124
184879 57764
214202 174723
260126 48900
223340 58692
245419 293251
17459 150796
127412 63828
66384 268920
28747 59343
5838 127804
19351 227286
264671 287778
169492 132276
229938 266412
226736 227730
3176 54179
242260 188192
134538 35594
45636 272101
170102 62331
63590 210599
253220 147981
293...

result:

ok Good Job! (1 test case)

Test #30:

score: 0
Accepted
time: 60ms
memory: 14204kb

input:

1
297687
114063 114325
61315 256781
17004 254276
279378 173674
50685 133866
254276 270764
254276 168958
160573 254276
183000 144763
254276 41646
138547 226105
254276 62934
250757 284583
254276 147160
254276 62486
163839 23030
246684 80048
219153 38897
254276 184254
297273 295022
146005 254276
229491...

output:

123999
170486 294514
277302 185246
151548 291140
38418 231339
199038 178538
145756 97340
11416 97685
182108 129505
244370 69805
281270 166973
124834 197453
132057 226810
254612 80824
30176 289491
240828 196418
183132 139080
161536 278069
9445 69975
210864 81245
139107 165656
172609 8362
215257 51258...

result:

ok Good Job! (1 test case)

Test #31:

score: 0
Accepted
time: 52ms
memory: 14860kb

input:

1
298467
24310 131068
270342 284416
110818 163791
140749 270342
200509 156894
128257 270342
286273 39457
230236 150598
48559 18558
271934 270342
270342 221456
270342 240611
146171 270342
142089 270342
265273 37099
4824 207615
273677 270342
270342 233942
131877 270342
282024 14594
58550 270342
3225 1...

output:

99500
157010 29667
275698 184623
168826 108251
175741 221699
266132 264566
288286 98659
224267 274099
200572 225317
1370 104800
41883 133683
32713 108538
279372 249242
200371 287403
101216 229641
252340 40271
101077 156259
23657 264100
23594 44139
249919 24562
254646 133443
57209 62852
216019 142798...

result:

ok Good Job! (1 test case)

Test #32:

score: 0
Accepted
time: 35ms
memory: 12632kb

input:

1
299096
43798 64829
64829 22308
25723 64829
125491 64829
132554 64829
64829 31091
82698 64829
161922 64829
64829 48363
153172 64829
198568 64829
64829 68075
246874 64829
64829 122620
64829 237999
64829 257438
44676 64829
64829 295759
64829 45750
64829 17755
195879 64829
86788 64829
172696 64829
648...

output:

-1

result:

ok Good Job! (1 test case)

Test #33:

score: 0
Accepted
time: 41ms
memory: 16092kb

input:

1
299097
55978 208819
55978 222666
55978 118386
176498 55978
177724 55978
55978 286400
7823 55978
55978 86011
258404 55978
55978 127466
55978 52857
34668 55978
31665 55978
55978 160320
55978 239002
290038 55978
55978 36827
55978 280050
55978 104777
55978 158847
52282 55978
206198 55978
55978 58412
1...

output:

149548
115578 257132
197746 280431
283255 266001
105491 255180
96231 283182
34528 58809
280524 12267
288146 288565
152293 122263
199576 265260
238077 292878
296354 269524
81312 143614
276110 36649
45649 137718
228585 36265
275568 281461
173733 167482
249230 28515
266671 183746
215839 257279
135939 1...

result:

ok Good Job! (1 test case)

Test #34:

score: 0
Accepted
time: 44ms
memory: 15488kb

input:

1
299097
166438 82625
82625 128838
82625 141580
83485 82625
82625 210941
82625 40444
82625 45514
112980 82625
82625 8971
82625 240680
53717 82625
82625 243508
275918 82625
82625 214884
80291 82625
82625 244056
278345 82625
82625 50552
82625 84626
234287 82625
227857 82625
82625 282783
82625 169441
1...

output:

149548
65891 272810
284438 168533
1773 44830
45536 89247
234754 224454
26496 175752
253553 97418
80862 272599
161897 181710
252048 178092
195304 94161
130395 90886
89984 102793
141496 152714
18763 180433
69713 233532
64627 47059
143600 177876
3519 270112
54312 246221
41739 94801
167394 260929
213166...

result:

ok Good Job! (1 test case)

Test #35:

score: 0
Accepted
time: 51ms
memory: 18624kb

input:

1
299097
260330 58892
133029 58892
58892 172471
42729 58892
58892 26074
58892 99490
58892 3974
59464 58892
58892 186328
119256 58892
225649 58892
162394 58892
58892 128284
58892 215895
281775 58892
275533 58892
58892 149488
167782 58892
22771 58892
58892 63000
58892 9677
83128 58892
58892 121018
588...

output:

149548
101082 153018
13893 60280
156195 2182
282301 154097
233607 36172
178422 75835
171123 54263
148250 296959
270356 73847
39979 181257
95981 88036
13333 290396
85091 104163
150819 61461
138126 82389
135359 3037
265411 162380
138907 29852
285976 136970
52265 43588
124756 77938
190790 29923
169468 ...

result:

ok Good Job! (1 test case)

Test #36:

score: 0
Accepted
time: 40ms
memory: 7976kb

input:

10
29462
10852 16001
15495 6444
21756 23481
23752 13053
21560 13691
9711 23194
24917 23476
13053 18916
5 8995
17585 23447
644 13053
27831 13053
22383 10656
15443 21538
10814 3308
4868 2089
23555 13053
25895 13053
12345 13893
13053 14041
13053 8611
4444 15324
23999 27186
27037 13053
23208 22273
22940...

output:

10814
3750 1223
22368 1044
8939 21383
11001 8392
27302 15661
18192 3527
7880 13313
398 19730
23175 22750
6179 18599
5435 14872
8434 28726
4346 7725
8233 17618
22132 16073
6123 3906
3924 29201
12847 11434
27871 16811
3421 3662
1221 28813
6867 19055
28580 8171
14595 23006
11543 5954
14504 3249
8517 48...

result:

ok Good Job! (10 test cases)

Test #37:

score: 0
Accepted
time: 38ms
memory: 9968kb

input:

100
2959
1769 2187
2304 2429
2635 1931
271 2342
1671 153
707 1154
2597 1668
1048 204
1242 1301
926 2013
1557 2752
488 1893
613 1809
1416 2395
120 1179
982 321
2686 86
2313 2009
878 848
1447 2207
728 1885
2812 1683
1290 1627
2701 135
933 1099
1719 393
2355 2519
1368 384
311 1080
823 1642
459 2670
266...

output:

145
1967 413
13 2711
2879 1510
2535 1497
2624 442
945 274
1131 1249
1500 2749
2660 423
2231 2769
1854 2590
1916 411
986 1867
2273 685
1216 1929
1400 372
957 837
950 2838
2515 1054
2614 1529
1384 1974
1865 913
651 2427
486 1075
1879 740
2397 638
1903 2888
804 2561
31 1302
2300 1359
1191 2334
1228 140...

result:

ok Good Job! (100 test cases)

Test #38:

score: 0
Accepted
time: 40ms
memory: 9776kb

input:

1000
294
200 192
200 46
43 256
85 47
98 12
127 200
111 127
257 124
168 32
45 274
197 49
200 27
144 38
156 256
148 202
200 80
31 248
35 66
282 128
60 200
189 37
88 54
238 280
44 245
46 263
220 53
144 200
200 55
58 184
200 153
84 173
31 284
24 170
200 211
22 244
232 242
200 208
188 26
139 154
251 104
...

output:

108
140 186
209 247
216 286
222 290
85 68
260 71
267 134
6 189
291 180
94 77
3 198
141 288
32 41
177 18
261 183
74 163
116 167
122 241
259 81
73 220
244 39
93 64
51 226
193 19
165 227
114 121
266 264
276 43
5 82
176 174
92 271
231 101
9 187
97 239
63 294
173 166
21 197
243 274
13 109
16 162
8 29
11 ...

result:

ok Good Job! (1000 test cases)

Test #39:

score: 0
Accepted
time: 75ms
memory: 14228kb

input:

1
299997
253129 238438
256990 147794
56683 265606
62100 74831
58006 231602
227120 138613
72936 16010
271383 221839
110579 31739
13864 11106
196180 159069
78858 61661
262511 279235
45738 172410
2512 6066
144552 29625
194524 184023
196218 229474
256817 33532
166763 175023
188106 91596
93278 158818
280...

output:

149998
89965 8364
231660 183635
72076 200088
99153 104670
286719 97781
167290 43537
137064 78383
104781 230198
200875 35421
91527 172947
179263 171884
278568 102115
296526 196189
45806 82812
154049 200983
136608 286648
157960 272312
209216 51854
84323 7151
190410 60871
206177 160373
64474 166519
205...

result:

ok Good Job! (1 test case)

Test #40:

score: 0
Accepted
time: 72ms
memory: 14640kb

input:

1
299995
251405 13382
21412 273614
170998 239060
142811 89087
163686 80590
54073 23173
29717 93866
155059 150414
171846 663
218307 10405
252692 83378
131202 289721
52385 252854
293096 280491
216796 237285
242784 243233
52784 6922
68312 26488
205497 147202
65036 297840
58601 67107
164525 57839
167843...

output:

149997
36504 208277
285890 63341
228702 95072
103293 291005
109006 153874
246573 131014
147091 212941
286094 84233
261209 126159
73938 59746
11479 18417
73696 289650
171909 223128
51376 200275
57210 132735
118440 1465
83598 29592
125949 1517
11507 61167
189592 118799
46804 105226
176358 68076
74153 ...

result:

ok Good Job! (1 test case)

Test #41:

score: 0
Accepted
time: 72ms
memory: 14460kb

input:

1
299993
5467 110867
249637 87281
209055 74176
170317 272027
19928 97403
158898 19368
120942 93881
150886 63314
221175 188504
125295 79790
241291 263489
258417 196595
157362 130040
163372 85682
261036 45856
257946 163512
54262 17552
251249 14029
213457 65927
265238 36030
4861 71772
159755 111439
375...

output:

149996
192918 85296
130683 285468
38771 204012
89703 92869
157162 102102
260060 66255
196195 3762
269749 158306
286549 183732
94117 124597
26440 166457
150749 33890
53576 122693
19929 19643
50357 31054
27686 38446
228713 299490
83899 283042
191791 256009
45274 32330
139187 63303
104648 230229
71843 ...

result:

ok Good Job! (1 test case)

Test #42:

score: 0
Accepted
time: 71ms
memory: 14476kb

input:

1
299991
248982 174625
105559 244297
35265 128781
206509 158409
13863 41023
249166 59270
215265 188850
218206 113138
126624 205065
241101 283870
31511 34427
237845 182965
134293 221193
214509 104965
67564 158810
198261 216053
115921 200242
245392 107170
62619 285117
48060 132083
166094 84748
150023 ...

output:

149995
26337 115014
112477 105363
141892 274965
232917 278819
5016 249697
260516 243178
273429 83258
19014 263118
212113 164707
123252 112323
35375 224878
199630 123462
268894 281175
82243 111395
101646 57991
256375 222087
89629 100731
93173 80089
135750 8694
271925 261385
241736 289059
221768 30732...

result:

ok Good Job! (1 test case)

Test #43:

score: 0
Accepted
time: 58ms
memory: 13408kb

input:

1
299999
185541 176688
252501 252009
201515 181336
174664 10052
235206 78841
271650 240453
177704 41444
30343 236755
136584 224074
123830 176470
119252 294416
176341 111829
241834 52983
35945 184402
68227 225761
146133 151540
249663 70136
156441 42951
95322 152829
259090 103376
84766 152588
150129 1...

output:

149999
46978 17037
46620 98884
162235 84748
139817 101540
25694 101229
105904 186750
164435 201082
221672 204237
216504 269705
22364 96979
139510 183154
67605 99071
220705 237857
273128 239996
58345 85768
273795 231001
137300 142261
168197 74337
127102 148115
187750 137450
210601 204690
109588 24855...

result:

ok Good Job! (1 test case)

Test #44:

score: 0
Accepted
time: 70ms
memory: 13952kb

input:

1
299997
46586 268160
120257 162918
155586 87070
233774 236522
195573 139640
213343 184602
26338 174317
236326 103114
246267 241694
166020 217647
73806 217138
115817 291894
296219 281396
231138 217264
57086 215561
296205 295067
174916 36910
262907 177629
268640 277927
33944 172724
299448 298104
2913...

output:

149998
144614 112082
181384 134167
242323 73274
139972 106076
86524 42793
88283 175592
186677 197623
228699 42788
62989 49314
33294 198946
110984 72866
215768 201593
252019 237172
148475 75142
61931 19691
181559 196203
81616 49156
232032 156186
44662 244672
142439 124497
138582 139247
30499 101775
2...

result:

ok Good Job! (1 test case)

Test #45:

score: 0
Accepted
time: 45ms
memory: 7936kb

input:

100
2997
1842 108
983 1626
2076 2280
1960 2673
2029 1154
1506 836
144 1843
173 1775
322 1567
1632 1092
2608 2819
2737 2888
24 2046
400 2487
2396 2569
2072 1695
2223 2237
2175 592
694 2236
2523 2322
2211 2325
2196 2888
1509 1586
2376 2272
2063 2310
2471 2612
2530 2101
1618 25
1830 1404
2646 743
2256 ...

output:

1498
50 1320
1126 1280
2417 1317
945 51
2036 134
2445 2070
2443 2768
1018 2791
172 1231
2256 12
1234 90
2510 2515
1127 228
1392 1609
1273 356
769 2079
2755 2562
2572 2784
2861 2894
598 1282
1657 616
1041 1098
978 971
1898 1917
2473 1941
967 589
1487 2421
2682 304
2491 2716
780 620
1266 669
1094 2184...

result:

ok Good Job! (100 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 19:11:16 | OpenSource Project