QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113828#5545. Contingency PlanPetroTarnavskyi#WA 31ms10732kbC++171.6kb2023-06-19 16:50:322023-06-19 16:50:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 16:50:32]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:10732kb
  • [2023-06-19 16:50:32]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 100447;
vector<PII> g[N];
int deg[N];
PII ans[N];
int root = 0;
int u = -1;
int n;


void dfs(int v, int idx, int h = 0)
{
	if (h == 0)
	{
		sort(ALL(g[v]), [&](PII a, PII b)
		{
			return deg[a.first] > deg[b.first];
		});
	}
	if (h >= 2)
	{
		if (u == -1) u = v;
		ans[idx] = {root, v};
	}
	int pr = -1, pi = -1;
	int mx = 0;
	for (auto& [to, i] :g[v])
	{
		mx = max(mx, i);
		if (i != idx)
		{
			dfs(to, i, h + 1);
			if (h == 0 && pr != -1)
			{
				ans[pi] = {pr, to};
			}
			pi = i;
			pr = to;
		}
	}
	if (h == 0)
	{
		ans[pi] = {pr, u};
		if (mx == deg[root] - 1)
		{
			FOR (i, 0, n)
			{
				if (ans[i] == MP(root, u))
				{
					swap(ans[i], ans[mx]);
					break;
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	FOR (i, 0, n - 1)
	{
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].PB({b, i});
		g[b].PB({a, i});
		deg[a]++, deg[b]++;
	}
	if (*max_element(deg, deg + n) == n - 1)
	{
		cout << -1 << '\n';
		return 0;
	}
	while (deg[root] == 1) root++;
	
	dfs(root, -1, 0);
	
	FOR (i, 0, n - 1)
	{
		cout << ans[i].first + 1 << ' ' << ans[i].second + 1 << '\n';
	}
	
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6204kb

input:

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

output:

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

result:

ok AC

Test #2:

score: 0
Accepted
time: 2ms
memory: 6156kb

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0
Accepted
time: 2ms
memory: 6048kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: 0
Accepted
time: 2ms
memory: 6612kb

input:

5
2 1
2 3
2 4
4 5

output:

1 3
3 5
2 5
4 1

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 3
3 2
4 2
5 1

result:

ok AC

Test #6:

score: 0
Accepted
time: 2ms
memory: 6220kb

input:

5
5 2
1 2
4 2
3 4

output:

5 1
1 3
2 3
4 5

result:

ok AC

Test #7:

score: 0
Accepted
time: 2ms
memory: 7176kb

input:

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

output:

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

result:

ok AC

Test #8:

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

input:

20000
7662 1
9205 1
5971 1
1 9886
1 18853
14108 1
998 1
1 14958
7100 1
1 2670
1 18493
13838 1
4644 1
2139 1
1 18540
1 14081
1 16836
1 9357
245 1
242 1
1 13472
1 1471
3792 1
1 17875
13976 1
1 15085
1 17283
15014 1
17477 1
11578 1
18441 1
1 14367
3018 1
1 7186
1 4939
2470 1
2993 1
6175 1
1 19886
1 125...

output:

7662 3346
9205 11578
5971 9205
9886 5971
18853 9886
14108 18853
998 14108
14958 998
7100 14958
2670 7100
18493 242
13838 13472
4644 13838
2139 4644
18540 2139
14081 18540
16836 14081
9357 16836
245 9357
242 245
13472 2670
1471 1107
3792 1471
17875 3792
13976 17875
15085 13976
17283 15085
15014 17283...

result:

ok AC

Test #9:

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

input:

20000
8854 1
15635 1
8088 1
1 12138
12367 1
1 15051
6392 1
15564 1
17334 1
1 10164
8704 1
1 13795
1 10292
12108 1
1 50
4 1
1 18364
13341 1
19203 1
1 3017
1 5133
3499 1
19202 1
1 10304
12975 1
1 17220
1 1716
1 4158
1 16763
1 301
1 16645
8690 1
1 10064
16977 1
1 19618
1 5471
1 8763
3997 1
1 3283
11332...

output:

8854 10691
15635 301
8088 15635
12138 8088
12367 12138
15051 12367
6392 15051
15564 6392
17334 15564
10164 17334
8704 3017
13795 5133
10292 13795
12108 10292
50 12108
4 50
18364 4
13341 18364
19203 13341
3017 19203
5133 10164
3499 14807
19202 3499
10304 19202
12975 10304
17220 12975
1716 17220
4158 ...

result:

ok AC

Test #10:

score: 0
Accepted
time: 6ms
memory: 6784kb

input:

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

output:

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

result:

ok AC

Test #11:

score: 0
Accepted
time: 7ms
memory: 6724kb

input:

20000
1 13291
13291 19998
3314 13291
13291 3339
13291 10237
13244 13291
13291 3392
13291 4459
13291 17335
13291 10356
6124 13291
13291 4470
12896 13291
13291 12094
3309 13291
13319 13291
13291 15658
13291 2305
13291 13710
13291 16520
13291 16234
6697 13291
13291 6686
9187 13291
13291 43
13291 2764
1...

output:

1064 1
1064 19998
1064 3314
1064 3339
1064 10237
1064 13244
1064 3392
1064 4459
1064 17335
1064 10356
1064 6124
1064 4470
1064 12896
1064 12094
1064 3309
1064 13319
1064 15658
1064 2305
1064 13710
1064 16520
1064 16234
1064 6697
1064 6686
1064 9187
1064 43
1064 2764
1064 9061
1064 8113
1064 8449
106...

result:

ok AC

Test #12:

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

input:

20000
4030 5565
1206 5565
5565 8947
4887 5565
14605 5565
5565 2947
5565 9038
5565 5326
5565 9021
11087 5565
5565 19562
895 5565
14653 5565
5565 10803
5565 9750
5565 16331
4689 5565
14307 5565
11631 5565
5565 13244
10554 5565
8112 5565
5565 9394
5565 5945
15279 5565
5565 15512
1334 5565
5565 6025
556...

output:

4030 2271
1206 3491
8947 1206
4887 8947
14605 4887
2947 14605
9038 2947
5326 9038
9021 5326
11087 9021
19562 13244
895 10554
14653 895
10803 14653
9750 10803
16331 9750
4689 16331
14307 4689
11631 14307
13244 11631
10554 11087
8112 1776
9394 8112
5945 9394
15279 5945
15512 15279
1334 15512
6025 1334...

result:

ok AC

Test #13:

score: 0
Accepted
time: 23ms
memory: 10568kb

input:

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

output:

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

result:

ok AC

Test #14:

score: 0
Accepted
time: 2ms
memory: 5812kb

input:

5
2 1
3 2
4 3
5 4

output:

1 4
2 4
3 1
2 5

result:

ok AC

Test #15:

score: 0
Accepted
time: 31ms
memory: 10588kb

input:

100000
21871 1
13678 1
27196 1
70437 1
1 35891
1 43010
28018 1
1 64489
61157 1
1 35572
1 41613
1 73049
93865 1
83507 1
1 92127
86278 1
1 15004
1 44154
2005 1
1 94210
41410 1
1 5886
69836 1
1 24120
1 80802
1 9940
66220 1
66549 1
1 20103
1 5
1 33021
35482 1
76185 1
34850 1
1 55173
1 72488
1 76286
1 99...

output:

21871 29202
13678 99583
27196 13678
70437 27196
35891 70437
43010 35891
28018 43010
64489 28018
61157 64489
35572 61157
41613 35572
73049 41613
93865 80802
83507 9940
92127 83507
86278 92127
15004 86278
44154 15004
2005 44154
94210 2005
41410 94210
5886 41410
69836 5886
24120 69836
80802 24120
9940 ...

result:

ok AC

Test #16:

score: 0
Accepted
time: 31ms
memory: 10732kb

input:

100000
1 12976
28108 1
87682 1
79359 1
16128 1
1 90652
1 55874
27276 1
1 66899
1 10296
1 37870
1 78978
26221 1
28589 1
1 46430
32252 1
22407 1
68230 1
64944 1
1 53457
31023 1
1 57101
1 82578
1 33273
69683 1
64357 1
1 32517
1 45623
1 29497
41082 1
1 43731
1 28620
1 64304
1 23462
1 81982
1 91877
1 309...

output:

12976 68390
28108 86781
87682 28108
79359 87682
16128 79359
90652 16128
55874 90652
27276 55874
66899 27276
10296 66899
37870 10296
78978 37870
26221 69683
28589 64357
46430 28589
32252 46430
22407 32252
68230 22407
64944 68230
53457 64944
31023 53457
57101 31023
82578 57101
33273 82578
69683 33273
...

result:

ok AC

Test #17:

score: 0
Accepted
time: 27ms
memory: 10632kb

input:

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

output:

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

result:

ok AC

Test #18:

score: 0
Accepted
time: 26ms
memory: 10548kb

input:

100000
15924 1
13919 15924
86413 15924
15924 78418
36904 15924
15924 60478
15924 78563
15924 23855
63531 15924
15574 15924
73713 15924
62532 15924
15924 19461
15924 80750
15924 57012
15924 27046
55780 15924
69619 15924
58970 15924
65824 15924
15924 3195
26782 15924
71411 15924
84915 15924
95347 1592...

output:

1 19978
13919 4974
86413 13919
78418 86413
36904 78418
60478 36904
78563 60478
23855 78563
63531 23855
15574 63531
73713 15574
62532 73713
19461 95347
80750 53739
57012 80750
27046 57012
55780 27046
69619 55780
58970 69619
65824 58970
3195 65824
26782 3195
71411 26782
84915 71411
95347 84915
53739 6...

result:

ok AC

Test #19:

score: 0
Accepted
time: 31ms
memory: 10528kb

input:

100000
40659 47250
51514 40659
40659 83613
16333 40659
25291 40659
40659 61711
40659 37621
40659 66805
40659 59550
67744 40659
40659 46644
40659 21771
40659 98164
40659 6655
75053 40659
90431 40659
40659 58023
48769 40659
11506 40659
19125 40659
52852 40659
98702 40659
53360 40659
40659 3999
66767 4...

output:

15917 47250
15917 51514
15917 83613
15917 16333
15917 25291
15917 61711
15917 37621
15917 66805
15917 59550
15917 67744
15917 46644
15917 21771
15917 98164
15917 6655
15917 75053
15917 90431
15917 58023
15917 48769
15917 11506
15917 19125
15917 52852
15917 98702
15917 53360
15917 3999
15917 66767
15...

result:

ok AC

Test #20:

score: 0
Accepted
time: 2ms
memory: 6820kb

input:

20000
13211 1
1 10767
13211 16998
13211 495
10767 7635
10767 6994
10669 16998
1369 16998
495 4745
722 495
7635 251
3552 7635
7267 6994
6994 1772
10669 18929
10669 9328
3076 1369
1369 14212
4745 284
4745 9599
722 6137
722 10565
15137 251
5349 251
16431 3552
3552 15719
7267 10917
598 7267
19533 1772
1...

output:

13211 10767
1 16998
10767 16998
1 495
1 7635
1 6994
1 10669
1 1369
1 4745
1 722
1 251
1 3552
1 7267
1 1772
1 18929
1 9328
1 3076
1 14212
1 284
1 9599
1 6137
1 10565
1 15137
1 5349
1 16431
1 15719
1 10917
1 598
1 19533
1 5233
1 13724
1 10707
1 7333
1 13598
1 9683
1 6305
1 16056
1 12864
1 16760
1 1895...

result:

ok AC

Test #21:

score: 0
Accepted
time: 6ms
memory: 6860kb

input:

20000
11262 14400
16805 2790
19084 11979
15259 5949
9916 12236
2445 1637
1905 15141
9540 16655
12812 16186
19052 1523
6643 1443
13738 10091
9218 1337
16617 16436
17295 16466
1171 1217
19150 5280
2830 8076
16135 7234
11460 213
8101 341
5438 6331
5029 14871
10725 2090
5998 12241
8902 3420
4340 7265
18...

output:

1 14400
1 16805
1 11979
1 5949
1 9916
1 2445
1 15141
1 16655
1 16186
1 1523
1 1443
1 10091
1 9218
1 16617
1 16466
1 1217
1 19150
1 2830
1 7234
1 11460
1 8101
1 6331
1 14871
1 10725
1 12241
1 8902
1 7265
1 5618
1 14867
1 741
1 19617
1 10801
1 12234
1 1508
1 18805
1 18298
1 8321
1 11096
1 12347
1 1363...

result:

ok AC

Test #22:

score: 0
Accepted
time: 5ms
memory: 7000kb

input:

20000
19272 1
19272 7240
6952 7240
6952 10594
12564 10594
12564 13132
14483 13132
14483 1891
9772 1891
16614 9772
14519 16614
12050 14519
4039 12050
4039 9679
8408 4039
12050 6797
17990 6797
6797 17659
14519 14985
16415 14985
1735 16415
16415 18821
14985 9402
9402 18947
9402 5386
17560 16614
17560 1...

output:

19272 327
1 7240
1 6952
1 10594
1 12564
1 13132
1 14483
1 1891
1 9772
1 16614
1 14519
1 12050
1 4039
1 9679
1 8408
1 6797
1 17990
1 17659
1 14985
1 16415
1 1735
1 18821
1 9402
1 18947
1 5386
1 17560
1 1094
1 7537
1 19700
1 9876
1 16466
1 11779
1 8212
1 793
1 12138
1 1491
1 3819
1 12635
1 8903
1 5872...

result:

ok AC

Test #23:

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

input:

20000
4410 1
7210 1
1 2389
4410 18377
4410 4507
7905 4410
7210 14849
12441 7210
7210 9005
17807 2389
2389 6619
2389 6604
6913 18377
5811 18377
7249 18377
4507 1582
4507 8857
4507 17635
10077 7905
7905 4687
8607 7905
14849 16870
14849 3298
14849 2376
12441 9009
12441 10729
19879 12441
9005 19790
7715...

output:

4410 7210
7210 2389
1 18377
2389 18377
1 4507
1 7905
1 14849
1 12441
1 9005
1 17807
1 6619
1 6604
1 6913
1 5811
1 7249
1 1582
1 8857
1 17635
1 10077
1 4687
1 8607
1 16870
1 3298
1 2376
1 9009
1 10729
1 19879
1 19790
1 7715
1 4016
1 18955
1 11427
1 8360
1 2365
1 19675
1 7633
1 7521
1 5414
1 16483
1 1...

result:

ok AC

Test #24:

score: 0
Accepted
time: 5ms
memory: 7884kb

input:

20000
7223 19213
12395 18674
16451 12980
18029 7848
16056 11920
6906 11077
3923 10662
9192 4837
17604 11135
16462 2457
18842 9770
15130 10251
19601 6770
7954 12079
7559 642
15051 17509
1146 18583
18196 17621
4980 8041
19973 15310
16834 11112
3176 8010
957 12737
4072 830
3194 1873
11400 3394
6914 806...

output:

1 19213
1 12395
1 12980
1 7848
1 11920
1 6906
1 3923
1 4837
1 11135
1 2457
1 9770
1 10251
1 6770
1 12079
1 7559
1 15051
1 1146
1 17621
1 8041
1 19973
1 11112
1 3176
1 957
1 830
1 3194
1 11400
1 6914
1 14516
1 15976
1 1868
1 19612
1 163
1 13285
1 3523
1 5435
1 11408
1 5989
1 17775
1 17594
1 15194
1 1...

result:

ok AC

Test #25:

score: 0
Accepted
time: 2ms
memory: 5796kb

input:

5
2 1
3 1
4 1
1 5

output:

-1

result:

ok AC

Test #26:

score: 0
Accepted
time: 3ms
memory: 7364kb

input:

20000
1 4794
4794 19823
8249 19823
8249 19672
16549 19672
13478 16549
3608 13478
3608 14623
14623 10303
19353 14623
14623 7999
3608 14367
14367 17910
14367 8488
16947 14367
3608 1121
1121 1836
13048 1121
17393 1121
11488 13478
11488 17346
8954 17346
17346 4922
17346 13440
11488 2278
16202 2278
593 2...

output:

4794 16167
1 19823
1 8249
1 19672
1 16549
1 13478
1 3608
1 14623
1 10303
1 19353
1 7999
1 14367
1 17910
1 8488
1 16947
1 1121
1 1836
1 13048
1 17393
1 11488
1 17346
1 8954
1 4922
1 13440
1 2278
1 16202
1 593
1 13598
1 12496
1 7488
1 8346
1 2126
1 4302
1 5211
1 4461
1 13940
1 11704
1 3287
1 2229
1 28...

result:

ok AC

Test #27:

score: 0
Accepted
time: 5ms
memory: 7068kb

input:

20000
1 17253
5390 1
1 10221
1 16259
8902 1
10509 1
1 16551
1 13314
1 12754
1 11707
1 7781
1 2105
1 18132
1 12907
1 5609
1 15234
1 18609
1 13919
1 13882
1 15621
1 1997
1 14002
1 18056
7498 1
13534 1
1530 1
1 14773
1 2001
1 10679
1 13745
6140 1
19975 1
14198 1
1 7536
5623 1
1 6120
1 6954
730 1
1 1601...

output:

17253 18308
5390 10221
10221 16259
16259 8902
8902 10509
10509 16551
16551 13314
13314 12754
12754 6120
11707 5390
7781 2105
2105 18132
18132 12907
12907 5609
5609 15234
15234 18609
18609 12046
13919 2001
13882 15621
15621 1997
1997 14002
14002 18056
18056 7498
7498 13534
13534 1530
1530 13919
14773...

result:

ok AC

Test #28:

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

input:

20000
5445 4016
925 12966
8179 19342
5779 1
9123 4530
5079 8720
8754 5478
17667 13748
7203 13819
10489 7645
8537 14929
4717 5427
239 4564
17407 14318
6756 7348
4638 17915
19455 15109
3853 19342
15246 17470
8228 16612
7726 13819
1 16617
16607 6208
6228 12081
1615 14545
11897 16624
7653 14499
7273 195...

output:

1 5445
1 12966
1 8179
5779 816
1 9123
1 5079
1 5478
1 13748
1 7203
1 7645
1 14929
1 4717
1 4564
1 14318
1 7348
1 17915
1 15109
1 3853
1 15246
1 8228
1 7726
16617 16624
1 16607
1 6228
1 1615
1 11897
1 14499
1 19530
1 15437
1 17582
1 9523
1 18894
1 7204
1 1183
1 6264
1 12776
1 10060
1 4195
1 15487
1 6...

result:

ok AC

Test #29:

score: 0
Accepted
time: 4ms
memory: 7164kb

input:

20000
1 10558
10558 7298
7298 3082
17807 7298
793 7298
11663 7298
12412 7298
10699 7298
7298 1146
2462 7298
7298 12577
11701 7298
7298 7622
3831 7298
19955 7298
3001 7298
7298 18329
7298 851
7298 16782
7298 17396
7298 15015
12771 7298
7298 10926
4736 7298
9088 7298
4867 7298
16066 7298
7298 2148
729...

output:

10558 16592
1 7298
1 3082
1 17807
1 793
1 11663
1 12412
1 10699
1 1146
1 2462
1 12577
1 11701
1 7622
1 3831
1 19955
1 3001
1 18329
1 851
1 16782
1 17396
1 15015
1 12771
1 10926
1 4736
1 9088
1 4867
1 16066
1 2148
1 9282
1 3101
1 1177
1 16186
1 18525
1 9265
1 10881
1 15895
1 14732
1 15331
1 10411
1 1...

result:

ok AC

Test #30:

score: 0
Accepted
time: 9ms
memory: 7664kb

input:

20000
1 11767
10226 11767
6246 10226
6576 6246
458 6576
458 5997
16052 5997
16052 10900
4370 10900
4370 17480
17480 11379
4859 11379
14663 4859
18363 14663
1454 18363
18490 1454
18490 17760
17760 19850
19832 19850
4252 19832
5482 4252
2802 5482
17779 2802
17779 8601
10844 8601
10844 17372
1230 17372...

output:

2 1
2 11767
2 10226
2 6246
2 6576
2 458
2 5997
2 16052
2 10900
2 4370
2 17480
2 11379
2 4859
2 14663
2 18363
2 1454
2 18490
2 17760
2 19850
2 19832
2 4252
2 5482
2 2802
2 17779
2 8601
2 10844
2 17372
2 1230
2 13019
2 3128
2 19136
2 9687
2 9016
2 12862
2 18082
2 14262
2 11849
2 3064
2 15552
2 3949
2 ...

result:

ok AC

Test #31:

score: -100
Wrong Answer
time: 10ms
memory: 8644kb

input:

20000
16653 18166
1123 17313
12716 14313
11207 7401
2794 831
480 7420
4462 1161
575 456
15192 3052
12389 7101
15729 18976
18772 19492
18805 2052
866 10412
8160 3697
13319 15062
19241 11526
11876 3502
613 17770
15035 14829
6518 16531
11665 19122
15722 18062
19841 14843
5758 3123
1633 14519
3637 13277...

output:

2 18166
2 17313
2 12716
2 11207
2 831
2 7420
2 1161
2 575
2 3052
2 7101
2 18976
2 18772
2 18805
2 866
2 8160
2 15062
2 19241
2 11876
2 613
2 14829
2 16531
2 11665
2 15722
2 14843
2 5758
2 14519
2 13277
2 14004
2 11487
2 383
2 18796
2 8073
2 14763
2 2091
2 12285
2 4132
2 19583
2 3795
2 12657
2 1595
2...

result:

wrong answer cycle detected