QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#255538#5545. Contingency Plansentheta#AC ✓46ms20056kbC++202.3kb2023-11-18 16:15:082023-11-18 16:15:09

Judging History

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

  • [2023-11-18 16:15:09]
  • 评测
  • 测评结果:AC
  • 用时:46ms
  • 内存:20056kb
  • [2023-11-18 16:15:08]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define int long long
#define pii pair<int,int>
#define pb emplace_back
#define rep(i,a,b) for(int i=a; i < b; ++i)
#define owo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define V vector

#define cerr if(1) cout
#define dbg(x) cerr << "?" << #x << " : " << x << endl;

void solve();
signed main(){
	owo
	int t = 1; //cin >> t
	while(t--) solve();
}

const int N = 1e5+5;


int n;
array<int,2> edg[N];
V<int> adj[N];

int r[4];

int d[N], p[N];
void dfs(int x,int par){
	for(int e : adj[x]){
		int y = edg[e][0]^edg[e][1]^x;
		if(y==par) continue;
		bool isr = 0;
		rep(i,0,4){
			isr |= y==r[i];
		}
		if(isr) continue;

		p[y] = p[x];
		d[y] = d[x]+1;
		dfs(y, x);
	}
}


bool g[4][4], gvis[4];
int gdfs(int x){
	if(gvis[x]) return 0;
	gvis[x] = 1;

	int ret = 1;
	rep(y,0,4) if(g[x][y]){
		ret += gdfs(y);
	}
	return ret;
}


void solve(){
	cin >> n;

	rep(e,1,n){
		int u, v;
		cin >> u >> v;

		edg[e] = {u,v};
		adj[u].push_back(e);
		adj[v].push_back(e);
	}

	r[1] = -1;
	rep(e,1,n){
		auto[u,v] = edg[e];
		if(adj[u].size()>=2 && adj[v].size()>=2){
			r[1] = u; r[2] = v; break;
		}
	}
	if(r[1]==-1){
		cout << -1 << '\n'; return;
	}

	for(int e : adj[r[1]]){
		int x = edg[e][0]^edg[e][1]^r[1];
		if(x!=r[2]){
			r[0] = x; break;
		}
	}
	for(int e : adj[r[2]]){
		int x = edg[e][0]^edg[e][1]^r[2];
		if(x!=r[1]){
			r[3] = x; break;
		}
	}

	rep(i,0,4){
		// dbg(r[i]);
		p[r[i]] = i;
		dfs(r[i], r[i]);
	}
	g[0][1] = g[1][2] = g[2][3] = 1;
	g[3][2] = g[2][1] = g[1][0] = 1;


	rep(e,1,n){
		auto[u,v] = edg[e];
		// dbg(u); dbg(v);

		if(d[u]==0 && d[v]==0){
			int i = p[u], j = p[v];
			g[i][j] = g[j][i] = 0;
			// dbg(i); dbg(j);

			bool found = 0;
			rep(ii,0,4) if(!found) rep(jj,0,ii-1) if(!found)
			if(!g[ii][jj]){
				// dbg(ii); dbg(jj);
				g[ii][jj] = g[jj][ii] = 1;
				gvis[0] = gvis[1] = gvis[2] = gvis[3] = 0;
				if(gdfs(0)==4){
					found = 1;
					cout << r[ii] << " " << r[jj] << "\n";
				}
				else{
					g[ii][jj] = g[jj][ii] = 0;
				}
			}
			assert(found);

		}
		else{
			if(!(d[u]<d[v])) swap(u,v);
			cout << v << " " << r[(p[v]+1)%4] << "\n";
		}

	}	


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0
Accepted
time: 0ms
memory: 5908kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

4 1
3 4
5 2
5 1

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

5 1
3 5
2 4
2 1

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 3
1 5
2 3
5 4

result:

ok AC

Test #7:

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

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:

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

result:

ok AC

Test #8:

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

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 17029
9205 7662
5971 7662
9886 7662
18853 7662
14108 7662
998 7662
14958 7662
7100 7662
2670 7662
18493 7662
13838 7662
4644 7662
2139 7662
18540 7662
14081 7662
16836 7662
9357 7662
245 7662
242 7662
13472 7662
1471 7662
3792 7662
17875 7662
13976 7662
15085 7662
17283 7662
15014 7662
17477 76...

result:

ok AC

Test #9:

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

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:

17288 8854
15635 17288
8088 17288
12138 17288
12367 17288
15051 17288
6392 17288
15564 17288
17334 17288
10164 17288
8704 17288
13795 17288
10292 17288
12108 17288
50 17288
4 17288
18364 17288
13341 17288
19203 17288
3017 17288
5133 17288
3499 17288
19202 17288
10304 17288
12975 17288
17220 17288
17...

result:

ok AC

Test #10:

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

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:

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

result:

ok AC

Test #11:

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

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:

1 19555
19998 1
3314 1
3339 1
10237 1
13244 1
3392 1
4459 1
17335 1
10356 1
6124 1
4470 1
12896 1
12094 1
3309 1
13319 1
15658 1
2305 1
13710 1
16520 1
16234 1
6697 1
6686 1
9187 1
43 1
2764 1
9061 1
8113 1
8449 1
3304 1
16249 1
3859 1
5651 1
8941 1
13460 1
19932 1
10868 1
10878 1
12114 1
2249 1
846...

result:

ok AC

Test #12:

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

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 9353
1206 4030
8947 4030
4887 4030
14605 4030
2947 4030
9038 4030
5326 4030
9021 4030
11087 4030
19562 4030
895 4030
14653 4030
10803 4030
9750 4030
16331 4030
4689 4030
14307 4030
11631 4030
13244 4030
10554 4030
8112 4030
9394 4030
5945 4030
15279 4030
15512 4030
1334 4030
6025 4030
19566 403...

result:

ok AC

Test #13:

score: 0
Accepted
time: 19ms
memory: 12420kb

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

result:

ok AC

Test #14:

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

input:

5
2 1
3 2
4 3
5 4

output:

1 4
2 4
1 3
5 3

result:

ok AC

Test #15:

score: 0
Accepted
time: 24ms
memory: 12580kb

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 99803
13678 21871
27196 21871
70437 21871
35891 21871
43010 21871
28018 21871
64489 21871
61157 21871
35572 21871
41613 21871
73049 21871
93865 21871
83507 21871
92127 21871
86278 21871
15004 21871
44154 21871
2005 21871
94210 21871
41410 21871
5886 21871
69836 21871
24120 21871
80802 21871
99...

result:

ok AC

Test #16:

score: 0
Accepted
time: 25ms
memory: 12584kb

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:

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

result:

ok AC

Test #17:

score: 0
Accepted
time: 20ms
memory: 12592kb

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:

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

result:

ok AC

Test #18:

score: 0
Accepted
time: 28ms
memory: 12400kb

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:

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

result:

ok AC

Test #19:

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

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:

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

result:

ok AC

Test #20:

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

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:

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

result:

ok AC

Test #21:

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

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:

14400 11979
16805 11979
11979 13507
5949 11979
9916 11979
2445 11979
15141 11979
16655 11979
16186 11979
1523 11979
1443 11979
10091 11979
9218 11979
16617 11979
16466 11979
1217 11979
19150 11979
2830 11979
7234 11979
11460 11979
8101 11979
6331 11979
14871 11979
10725 11979
12241 11979
8902 11979
...

result:

ok AC

Test #22:

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

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:

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

result:

ok AC

Test #23:

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

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:

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

result:

ok AC

Test #24:

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

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:

19213 11920
12395 11920
12980 11920
7848 11920
11920 10423
6906 11920
3923 11920
4837 11920
11135 11920
2457 11920
9770 11920
10251 11920
6770 11920
12079 11920
7559 11920
15051 11920
1146 11920
17621 11920
8041 11920
19973 11920
11112 11920
3176 11920
957 11920
830 11920
3194 11920
11400 11920
6914...

result:

ok AC

Test #25:

score: 0
Accepted
time: 0ms
memory: 6080kb

input:

5
2 1
3 1
4 1
1 5

output:

-1

result:

ok AC

Test #26:

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

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
19823 16167
8249 16167
19672 16167
16549 16167
13478 16167
3608 16167
14623 16167
10303 16167
19353 16167
7999 16167
14367 16167
17910 16167
8488 16167
16947 16167
1121 16167
1836 16167
13048 16167
17393 16167
11488 16167
17346 16167
8954 16167
4922 16167
13440 16167
2278 16167
16202 1616...

result:

ok AC

Test #27:

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

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 5390
3238 1
10221 17253
16259 17253
8902 17253
10509 17253
16551 17253
13314 17253
12754 17253
11707 17253
7781 17253
2105 17253
18132 17253
12907 17253
5609 17253
15234 17253
18609 17253
13919 17253
13882 17253
15621 17253
1997 17253
14002 17253
18056 17253
7498 17253
13534 17253
1530 17253
1...

result:

ok AC

Test #28:

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

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:

5445 16617
12966 16617
8179 16617
1 7204
9123 16617
5079 16617
5478 16617
13748 16617
7203 16617
7645 16617
14929 16617
4717 16617
4564 16617
14318 16617
7348 16617
17915 16617
15109 16617
3853 16617
15246 16617
8228 16617
7726 16617
16617 7204
16607 16617
6228 16617
1615 16617
11897 16617
14499 166...

result:

ok AC

Test #29:

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

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 11495
7298 11495
3082 11495
17807 11495
793 11495
11663 11495
12412 11495
10699 11495
1146 11495
2462 11495
12577 11495
11701 11495
7622 11495
3831 11495
19955 11495
3001 11495
18329 11495
851 11495
16782 11495
17396 11495
15015 11495
12771 11495
10926 11495
4736 11495
9088 11495
4867 11495
16...

result:

ok AC

Test #30:

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

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:

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

result:

ok AC

Test #31:

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

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:

18166 4595
1123 16653
12716 16653
11207 4595
2794 16653
7420 4595
1161 4595
575 16653
3052 4595
12389 16653
15729 16653
19492 16653
2052 16653
866 16653
3697 16653
13319 16653
19241 16653
3502 16653
613 4595
15035 16653
16531 4595
11665 4595
15722 4595
14843 16653
3123 16653
14519 4595
13277 16653
1...

result:

ok AC

Test #32:

score: 0
Accepted
time: 0ms
memory: 8360kb

input:

20000
5613 1
1 999
1 16709
1 2491
9549 1
19706 1
1 1022
1 3884
1 1916
6627 1
1 1600
10265 1
1 19100
19766 1
1 7450
1 14375
5986 1
10295 1
8625 1
11810 1
1 15542
1 5745
3506 1
12842 1
1 11860
1 16317
1 6553
12476 1
1 6031
8445 1
6462 1
1 1601
1 3014
14100 1
1 6771
1 2360
1 15402
4549 1
6116 1
1 17848...

output:

-1

result:

ok AC

Test #33:

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

input:

20000
2509 13795
17043 13795
12006 13795
13795 822
3022 13795
8572 13795
2579 13795
13795 9673
12654 13795
4181 13795
13795 15912
13795 8902
13795 19201
5015 13795
243 13795
13795 6524
13795 9461
16403 13795
13795 18444
1316 13795
15366 13795
13795 17126
13795 309
13795 10938
13795 1255
13795 5588
1...

output:

-1

result:

ok AC

Test #34:

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

input:

20000
12144 2902
8713 11740
8870 10266
6116 3885
5943 8380
10496 956
14162 9193
4497 3275
5480 4601
6858 17285
1067 3003
19501 1958
5579 12167
844 12167
5372 16648
18876 13545
6559 10656
2910 6918
5632 16656
10135 11948
11253 13524
10068 15948
17884 3833
6830 16257
1248 6924
9806 14359
11033 8077
86...

output:

12144 12167
8713 12167
10266 12167
6116 12167
5943 12167
10496 12167
9193 12167
4497 12167
5480 12167
6858 12167
3003 12167
1958 12167
5579 18929
12167 18929
16648 12167
18876 12167
10656 12167
6918 12167
5632 12167
10135 12167
11253 12167
10068 12167
3833 12167
16257 12167
6924 12167
9806 12167
807...

result:

ok AC

Test #35:

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

input:

20000
1284 10854
1436 9770
17852 14859
19561 13068
19123 19730
8297 15453
7167 3888
5853 15710
18440 5611
9368 5242
6667 12315
19899 12021
13550 19105
16314 1977
18051 11095
4122 16348
1987 4873
14613 10548
375 11649
6442 1199
228 18390
4006 7870
2115 10763
13056 1980
4042 9649
11446 10078
14111 289...

output:

10854 8188
1436 7124
17852 7124
13068 7124
19730 7124
15453 7124
3888 7124
5853 7124
18440 7124
5242 7124
12315 7124
12021 7124
19105 7124
1977 7124
11095 7124
4122 7124
4873 7124
10548 7124
11649 7124
1199 7124
228 7124
4006 7124
10763 7124
1980 7124
9649 7124
11446 7124
14111 7124
14896 7124
6991 ...

result:

ok AC

Test #36:

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

input:

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

output:

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

result:

ok AC

Test #37:

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

input:

20000
1 1914
16448 1914
16448 447
1 19785
19232 19785
17236 19785
12409 17236
11707 12409
15526 11707
15526 12645
19367 12645
19367 7871
12617 7871
658 7871
2936 7871
10186 2936
10186 12483
4222 12483
4222 6106
3280 6106
7313 6106
17305 6106
2244 17305
17305 18735
16748 6106
16748 1554
16748 1261
73...

output:

1914 19785
16448 19785
447 19785
16448 1
19232 1
17236 1
12409 1
11707 1
15526 1
12645 1
19367 1
7871 1
12617 1
658 1
2936 1
10186 1
12483 1
4222 1
6106 1
3280 1
7313 1
17305 1
2244 1
18735 1
16748 1
1554 1
1261 1
7318 1
9524 1
7917 1
6734 1
18980 1
13963 1
17414 1
18244 1
12882 1
13768 1
221 1
1732...

result:

ok AC

Test #38:

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

input:

20000
8234 1
16079 8234
18825 16079
18825 12361
12361 6709
6709 10905
12205 10905
3916 12205
16311 3916
16423 16311
16423 10094
10094 9710
1474 9710
1474 18631
18631 13459
6640 13459
19380 6640
19380 6320
19874 6320
2212 19874
2212 8880
8880 2809
15348 2809
14869 15348
14869 8029
924 8029
924 10270
...

output:

1 18825
8234 18825
1 16079
12361 16079
6709 16079
10905 16079
12205 16079
3916 16079
16311 16079
16423 16079
10094 16079
9710 16079
1474 16079
18631 16079
13459 16079
6640 16079
19380 16079
6320 16079
19874 16079
2212 16079
8880 16079
2809 16079
15348 16079
14869 16079
8029 16079
924 16079
10270 160...

result:

ok AC

Test #39:

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

input:

20000
3828 10203
17892 5873
17224 10321
12241 7554
2948 6507
17619 16861
11410 1012
17019 18616
13582 19398
16411 15552
578 14161
9621 19542
9684 1699
16733 9223
16474 19501
15178 3217
9743 11111
6539 14379
5655 12001
10637 2251
13411 7006
7104 9228
15833 19339
12622 4315
19092 7490
8033 12870
19399...

output:

3828 17892
5873 16399
10321 17892
7554 17892
6507 17892
17619 17892
1012 17892
18616 17892
19398 17892
16411 17892
578 17892
9621 17892
9684 17892
16733 17892
19501 17892
3217 17892
11111 17892
6539 17892
12001 17892
2251 17892
13411 17892
9228 17892
15833 17892
4315 17892
19092 17892
8033 17892
110...

result:

ok AC

Test #40:

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

input:

20000
6712 1
6712 16871
8572 16871
8572 10641
10641 16702
16702 18095
14014 18095
14014 10577
10577 1956
1956 13463
4593 13463
4593 17604
8524 17604
8524 4625
4625 5906
5906 17983
17983 13029
13029 7366
13038 7366
13038 3804
3804 3699
3699 15717
15717 967
16443 967
16443 1797
3079 1797
9213 3079
232...

output:

1 16871
2833 6712
8572 6712
10641 6712
16702 6712
18095 6712
14014 6712
10577 6712
1956 6712
13463 6712
4593 6712
17604 6712
8524 6712
4625 6712
5906 6712
17983 6712
13029 6712
7366 6712
13038 6712
3804 6712
3699 6712
15717 6712
967 6712
16443 6712
1797 6712
3079 6712
9213 6712
232 6712
16743 6712
1...

result:

ok AC

Test #41:

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

input:

20000
2591 11751
5562 1300
9597 7814
11201 6762
9942 6089
18201 10054
14040 17666
14050 3479
2754 6286
5122 10070
2705 10053
3703 8076
33 13628
18330 17144
15031 16159
668 10414
14591 4857
15396 13207
6623 13987
3946 9270
15622 17484
4063 8811
12866 7551
3439 8748
10982 6076
15522 1678
8947 4749
677...

output:

11751 18150
1300 18150
9597 18150
6762 18150
6089 18150
10054 18150
17666 18150
14050 18150
2754 18150
10070 18150
10053 18150
3703 18150
13628 18150
17144 18150
15031 18150
10414 18150
4857 11201
15396 18150
6623 18150
3946 18150
17484 18150
8811 18150
7551 18150
3439 18150
6076 11201
1678 18150
47...

result:

ok AC

Test #42:

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

input:

100000
1 72500
1 89151
72500 50542
16422 72500
31678 89151
89151 54297
19071 50542
25039 50542
59896 16422
57305 16422
17263 31678
31678 3514
54297 25341
13381 54297
19071 7507
15806 19071
25039 62775
20433 25039
59896 28013
59896 2793
84857 57305
57305 84225
17263 6434
17263 61853
37741 3514
3514 8...

output:

72500 89151
50542 1
50542 89151
16422 50542
31678 1
54297 1
19071 89151
25039 89151
59896 50542
57305 50542
17263 1
3514 1
25341 1
13381 1
7507 89151
15806 89151
62775 89151
20433 89151
28013 50542
2793 50542
84857 50542
84225 50542
6434 1
61853 1
37741 1
83001 1
44061 1
13085 1
58193 1
55647 1
7795...

result:

ok AC

Test #43:

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

input:

100000
37174 25594
26356 56758
70911 5299
53571 20298
89704 67180
69629 74497
31785 14492
10546 1814
71677 54029
2466 28838
57294 23003
35667 41920
5998 95159
14430 34895
74794 85483
87138 10195
54295 96087
21621 26770
92353 70922
56725 17254
67745 92044
30390 34948
64685 31050
54736 78533
63644 859...

output:

25594 380
26356 54691
70911 54691
20298 54691
89704 54691
74497 54691
14492 54691
10546 54691
71677 54691
28838 54691
23003 54691
41920 54691
95159 54691
34895 54691
74794 54691
10195 54691
54295 54691
21621 54691
70922 54691
56725 54691
67745 54691
30390 54691
31050 54691
78533 54691
8591 54691
415...

result:

ok AC

Test #44:

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

input:

100000
90403 1
90403 84049
84049 28339
50038 28339
50038 23735
23735 87291
87291 26404
26404 3276
3276 37488
67144 37488
67144 15335
15335 73596
32815 73596
58348 32815
32340 58348
77042 32340
32340 17210
58348 68281
68281 13360
68281 52957
32815 3781
88746 3781
33513 88746
88746 23338
11895 3781
90...

output:

1 84049
31209 90403
28339 90403
50038 90403
23735 90403
87291 90403
26404 90403
3276 90403
37488 90403
67144 90403
15335 90403
73596 90403
32815 90403
58348 90403
32340 90403
77042 90403
17210 90403
68281 90403
13360 90403
52957 90403
3781 90403
88746 90403
33513 90403
23338 90403
11895 90403
90021 ...

result:

ok AC

Test #45:

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

input:

100000
10753 1
31716 1
1 8354
41344 10753
10753 22340
33736 10753
31716 74747
24655 31716
31716 93736
4454 8354
65308 8354
36992 8354
53743 41344
59301 41344
41344 86462
22340 77782
22340 49193
90415 22340
33736 2126
72574 33736
33736 98153
92064 74747
23614 74747
74747 96121
24655 95702
47727 24655...

output:

1 41344
31716 41344
8354 31716
31716 10753
22340 1
33736 1
74747 41344
24655 41344
93736 41344
4454 31716
65308 31716
36992 31716
53743 10753
59301 10753
86462 10753
77782 1
49193 1
90415 1
2126 1
72574 1
98153 1
92064 41344
23614 41344
96121 41344
95702 41344
47727 41344
49727 41344
66140 41344
856...

result:

ok AC

Test #46:

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

input:

100000
82182 59525
43093 74187
83434 62328
30609 75691
98351 97443
93951 9234
89762 57868
66707 24839
91314 82444
9148 12031
46318 817
9254 56692
67828 19158
29614 79432
64090 86748
43645 44758
91501 26481
13108 70283
53676 76180
2183 16343
17086 64156
13813 38661
1934 69441
21652 50770
62980 13969
...

output:

82182 83216
74187 83216
83434 83216
30609 83216
97443 83216
9234 99953
57868 83216
24839 83216
91314 83216
9148 83216
817 83216
56692 83216
67828 83216
79432 83216
64090 83216
44758 83216
26481 83216
70283 83216
76180 83216
2183 83216
17086 83216
38661 83216
69441 83216
50770 83216
13969 83216
32887...

result:

ok AC

Test #47:

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

input:

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

output:

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

result:

ok AC

Test #48:

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

input:

100000
1 59819
46211 59819
46211 78631
78631 6887
6887 15685
45496 15685
45496 38399
38399 43932
22491 43932
22491 57782
25655 57782
57782 81578
40906 57782
22491 8185
8185 92518
96199 8185
63790 8185
22491 64847
84427 64847
34665 64847
30015 64847
34952 43932
34952 12997
41447 12997
19357 12997
307...

output:

59819 27108
46211 27108
78631 27108
6887 27108
15685 27108
45496 27108
38399 27108
43932 27108
22491 27108
57782 27108
25655 27108
81578 27108
40906 27108
8185 27108
92518 27108
96199 27108
63790 27108
64847 27108
84427 27108
34665 27108
30015 27108
34952 27108
12997 27108
41447 27108
19357 27108
30...

result:

ok AC

Test #49:

score: 0
Accepted
time: 24ms
memory: 13436kb

input:

100000
70720 1
71027 1
48338 1
1 61809
1 79963
1 39740
86644 1
14939 1
39918 1
41470 1
23364 1
1 54664
1 96370
1 53835
1 67313
33696 1
44243 1
50423 1
1 70539
73776 1
560 1
98363 1
71623 1
72365 1
1 73548
1 82843
1 64083
52686 1
1 44452
1 94601
1 43725
88136 1
1 65340
30989 1
1 94282
76705 1
1 4208
...

output:

1 17348
71027 17348
48338 71027
61809 71027
79963 71027
39740 71027
86644 71027
14939 71027
39918 71027
41470 71027
23364 71027
54664 71027
96370 71027
53835 71027
67313 71027
33696 71027
44243 71027
50423 71027
70539 71027
73776 71027
560 71027
98363 71027
71623 71027
72365 71027
73548 71027
82843 ...

result:

ok AC

Test #50:

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

input:

100000
55448 49209
4084 16405
52470 22193
57007 13008
43787 82824
91893 67413
72105 89438
5791 85302
74502 44950
57906 11997
53465 42216
63894 41770
20892 54078
19530 68055
34937 22893
43941 47065
54015 53196
91519 81132
80483 71834
1399 53196
18226 23550
46619 51969
78131 47878
85576 60764
37319 88...

output:

55448 46047
4084 46047
22193 46047
13008 46047
82824 46047
91893 46047
72105 46047
5791 46047
44950 46047
11997 46047
42216 46047
41770 46047
20892 46047
68055 46047
22893 46047
47065 46047
54015 46047
91519 46047
80483 46047
1399 46047
23550 46047
46619 46047
47878 46047
85576 46047
37319 46047
321...

result:

ok AC

Test #51:

score: 0
Accepted
time: 25ms
memory: 13532kb

input:

100000
1 13485
13485 21238
21238 89751
21238 74621
14404 21238
60040 21238
21238 46089
46928 21238
73214 21238
88224 21238
47403 21238
21238 99205
89778 21238
21238 89464
22870 21238
21238 75159
40123 21238
33512 21238
21238 30257
70298 21238
21238 79591
57804 21238
21238 99840
64087 21238
12717 212...

output:

13485 34302
21238 34302
89751 34302
74621 34302
14404 34302
60040 34302
46089 34302
46928 34302
73214 34302
88224 34302
47403 34302
99205 34302
89778 34302
89464 34302
22870 34302
75159 34302
40123 34302
33512 34302
30257 34302
70298 34302
79591 34302
57804 34302
99840 34302
64087 34302
12717 34302
...

result:

ok AC

Test #52:

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

input:

100000
43730 1
43730 8413
8413 13508
53025 13508
44444 53025
44444 46747
54535 46747
54535 16058
16058 27066
27066 73721
35961 73721
18398 35961
18398 3188
3188 9998
57229 9998
57229 96831
2109 96831
2109 89059
89059 89520
89520 62512
62512 9136
9136 32949
27353 32949
19993 27353
19993 17305
91005 1...

output:

8413 1
13508 43730
13508 1
53025 1
44444 1
46747 1
54535 1
16058 1
27066 1
73721 1
35961 1
18398 1
3188 1
9998 1
57229 1
96831 1
2109 1
89059 1
89520 1
62512 1
9136 1
32949 1
27353 1
19993 1
17305 1
91005 1
89369 1
44544 1
62632 1
97627 1
63485 1
91766 1
7276 1
21832 1
27796 1
99690 1
25279 1
82445 ...

result:

ok AC

Test #53:

score: 0
Accepted
time: 46ms
memory: 16672kb

input:

100000
5616 54215
70847 24268
13256 88765
87054 72678
65173 1284
61132 24104
29759 37270
50005 62107
8909 58386
97772 68628
3463 41963
93835 10608
7780 68599
97385 40426
52295 15155
65521 84045
97372 22218
24089 69011
44236 64952
21273 33469
21618 31458
76924 4738
27278 21658
6790 18294
2343 82355
8...

output:

54215 78572
24268 78572
88765 78572
72678 78572
1284 78572
61132 78572
29759 5616
50005 78572
58386 5616
97772 78572
3463 78572
10608 78572
68599 5616
40426 5616
52295 5616
84045 5616
22218 5616
69011 78572
64952 5616
21273 5616
31458 78572
76924 5616
27278 5616
18294 78572
2343 78572
9539 78572
103...

result:

ok AC

Test #54:

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

input:

100000
1 81565
21567 1
86484 1
95714 1
1 93565
1 15812
51087 1
15941 1
36746 1
1 34149
1 71887
1 61269
1 93111
1 52394
8732 1
1 62378
1 74176
1362 1
15806 1
91535 1
1 77121
1 17356
1 23401
70673 1
1 21367
77472 1
1 44692
1 45094
1 43652
62628 1
1 81187
1 98635
2258 1
1 491
1 1963
1 83580
12393 1
1 5...

output:

-1

result:

ok AC

Test #55:

score: 0
Accepted
time: 18ms
memory: 11256kb

input:

100000
62999 54230
62172 54230
54230 87813
80978 54230
54230 13635
8808 54230
34109 54230
54230 13451
54230 30179
9847 54230
93260 54230
54230 45610
54230 7282
54230 42958
54230 54480
54230 62452
54230 95890
32418 54230
54230 8456
54230 64404
54230 40018
54230 70843
38010 54230
57364 54230
95022 542...

output:

-1

result:

ok AC

Test #56:

score: 0
Accepted
time: 32ms
memory: 12844kb

input:

100000
85431 10525
82137 81079
48778 58755
215 90110
51120 51131
16823 69899
6320 72931
65015 30930
68354 78098
32070 13344
55633 13621
69157 69872
92675 79903
96312 24145
13234 89857
62310 15217
7671 50027
34561 73029
90324 42836
14988 3767
96314 18015
665 82164
49080 34432
24022 62814
89664 13182
...

output:

85431 46358
81079 46358
48778 46358
215 46358
51131 46358
16823 46358
72931 46358
30930 46358
78098 46358
13344 46358
13621 46358
69157 46358
79903 46358
24145 46358
13234 46358
15217 46358
7671 46358
73029 46358
90324 46358
3767 46358
18015 46358
665 46358
49080 46358
24022 46358
13182 46358
34581 ...

result:

ok AC

Test #57:

score: 0
Accepted
time: 28ms
memory: 12788kb

input:

100000
54861 12509
16932 42872
34657 39417
13373 37054
53410 71695
2271 28730
77047 80422
7187 34867
94140 69441
47384 90599
15092 60892
94502 35186
58059 98865
46037 92080
96465 56648
81008 245
86644 72226
35703 96730
7922 3613
97616 90536
41294 92557
22776 10335
74308 16656
86493 81735
91472 93048...

output:

12509 37054
42872 37054
34657 37054
37054 58408
53410 37054
28730 37054
77047 37054
7187 37054
94140 37054
47384 37054
60892 37054
35186 37054
98865 37054
46037 37054
96465 37054
245 37054
86644 37054
96730 37054
3613 37054
97616 37054
41294 37054
22776 37054
74308 37054
81735 37054
93048 37054
7645...

result:

ok AC

Test #58:

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

input:

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

output:

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

result:

ok AC

Test #59:

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

input:

100000
88390 1
1 51242
1 73844
73844 82993
69357 82993
82993 89153
89153 92016
36977 89153
75137 36977
82993 53533
97404 53533
49989 97404
67125 49989
53533 7006
7006 63635
60387 7006
59312 60387
24309 59312
26526 24309
24309 9985
9985 26403
60387 55203
55203 79993
79993 71230
71230 52071
52071 8306...

output:

73844 88390
51242 73844
82993 1
82993 88390
69357 88390
89153 88390
92016 88390
36977 88390
75137 88390
53533 88390
97404 88390
49989 88390
67125 88390
7006 88390
63635 88390
60387 88390
59312 88390
24309 88390
26526 88390
9985 88390
26403 88390
55203 88390
79993 88390
71230 88390
52071 88390
83065 ...

result:

ok AC

Test #60:

score: 0
Accepted
time: 28ms
memory: 16752kb

input:

100000
1 7264
7264 69649
85097 69649
29848 85097
29848 68683
68683 42523
15272 42523
97689 15272
97689 7996
30390 7996
54151 30390
22264 54151
22264 98123
98123 16751
27570 16751
9987 27570
9987 86950
86950 67445
67445 87275
8871 87275
8871 74967
74967 53362
53362 10217
10217 52404
45262 52404
45262...

output:

69649 1
85097 7264
85097 1
29848 1
68683 1
42523 1
15272 1
97689 1
7996 1
30390 1
54151 1
22264 1
98123 1
16751 1
27570 1
9987 1
86950 1
67445 1
87275 1
8871 1
74967 1
53362 1
10217 1
52404 1
45262 1
72843 1
86772 1
18694 1
30955 1
43425 1
68130 1
6209 1
97483 1
6778 1
29735 1
60476 1
16825 1
11463 ...

result:

ok AC

Test #61:

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

input:

100000
3518 47523
14887 83452
31336 87320
47772 87482
71420 24559
99732 17539
45904 20872
52728 70439
38581 75203
18345 49294
7385 74056
95971 72826
48547 37020
61306 27212
53241 59530
32550 2892
5369 8488
4000 50453
45119 41435
5899 77096
19235 37917
75044 40239
44198 79848
23637 99807
40855 52471
...

output:

47523 66509
14887 66509
87320 66509
87482 66509
71420 66509
99732 66509
20872 66509
70439 66509
38581 66509
49294 66509
7385 66509
95971 66509
37020 66509
61306 66509
53241 66509
2892 66509
8488 66509
50453 66509
45119 66509
77096 66509
37917 66509
40239 66509
79848 66509
99807 66509
52471 66509
245...

result:

ok AC

Test #62:

score: 0
Accepted
time: 32ms
memory: 16640kb

input:

100000
56405 1
56405 66063
66801 66063
66801 9845
9845 42911
42911 64818
67482 64818
35942 67482
35942 75546
75546 4505
4505 45628
45628 29159
29159 29378
83665 29378
83665 85205
85205 94326
78400 94326
91544 78400
92293 91544
95489 92293
20854 95489
20854 94810
91796 94810
91796 49331
49331 66242
9...

output:

1 66063
8284 56405
66801 56405
9845 56405
42911 56405
64818 56405
67482 56405
35942 56405
75546 56405
4505 56405
45628 56405
29159 56405
29378 56405
83665 56405
85205 56405
94326 56405
78400 56405
91544 56405
92293 56405
95489 56405
20854 56405
94810 56405
91796 56405
49331 56405
66242 56405
9479 56...

result:

ok AC

Test #63:

score: 0
Accepted
time: 43ms
memory: 15248kb

input:

100000
29993 41605
84963 10140
60237 62389
66780 93449
98439 1174
75487 87344
56945 1098
7281 10192
90231 22033
95031 94597
88728 56965
74791 64971
68584 15462
91264 43556
80943 25018
89575 23985
46970 91618
7237 89928
26433 7488
10258 93471
44420 34919
39007 60649
64537 14238
89107 56906
58805 7576...

output:

41605 853
84963 86483
62389 29993
66780 29993
98439 86483
87344 29993
1098 86483
7281 86483
90231 86483
95031 86483
88728 29993
64971 86483
15462 29993
91264 86483
80943 86483
89575 86483
46970 86483
7237 29993
26433 29993
93471 29993
44420 86483
60649 86483
14238 86483
56906 86483
75769 86483
48637...

result:

ok AC

Test #64:

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

input:

100000
87758 1
87758 8566
8566 53230
53230 68035
45464 68035
43933 45464
7611 43933
7611 72530
72530 97898
97898 68231
2236 84498
71861 63091
76814 62314
24969 43571
98738 76356
71858 14301
12495 4041
49101 10912
83218 63817
60387 86854
59093 27607
35192 6135
76119 58917
15976 50822
5377 60508
39902...

output:

8566 1
53230 87758
53230 1
68035 1
45464 1
43933 1
7611 1
72530 1
97898 1
68231 1
84498 1
71861 1
76814 1
43571 1
76356 1
14301 1
4041 1
49101 1
63817 1
86854 1
59093 1
35192 1
76119 1
50822 1
5377 1
39902 1
62754 1
47841 1
23602 1
65106 1
72292 1
97173 1
64193 1
46660 1
64231 1
74997 1
7293 1
53179...

result:

ok AC

Test #65:

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

input:

100000
49400 1
1 55311
78355 1
58471 1
25325 1
8216 1
19123 1
47311 1
1 87302
68137 1
1 98931
11168 1
1 42489
44803 1
25464 1
34243 1
63702 1
29572 1
14941 1
1 46103
1 54830
43707 1
57172 1
1 17538
75154 1
67663 1
1 6784
14487 1
45840 1
1 82849
1 77260
1 18850
1 7003
1 76083
16640 1
54748 1
46731 1
...

output:

33574 49400
55311 33574
78355 33574
58471 33574
25325 33574
8216 33574
19123 33574
47311 33574
87302 33574
68137 33574
98931 33574
11168 33574
42489 33574
44803 33574
25464 33574
34243 33574
63702 33574
29572 33574
14941 33574
46103 33574
54830 33574
43707 33574
57172 33574
17538 33574
75154 33574
6...

result:

ok AC

Test #66:

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

input:

100000
59098 1
88393 1
10097 1
1 27732
12542 1
1 74984
63414 1
1 68750
1 38087
65706 38087
46675 927
57918 60950
11844 60891
1200 51250
17750 31241
12177 66972
57772 85920
49826 92407
3739 18636
15328 31458
47706 69254
95722 85793
92734 12473
72338 65624
66312 27618
47426 68757
39713 32969
50029 618...

output:

38087 59098
88393 38087
10097 38087
27732 38087
12542 38087
74984 38087
63414 38087
68750 38087
65706 1
65706 59098
46675 59098
60950 59098
60891 59098
51250 59098
17750 59098
66972 59098
57772 59098
49826 59098
3739 59098
31458 59098
47706 59098
85793 59098
12473 59098
72338 59098
27618 59098
68757...

result:

ok AC

Test #67:

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

input:

5
2 1
1 3
4 1
5 4

output:

2 5
3 2
1 5
2 4

result:

ok AC

Test #68:

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

input:

5
4 1
3 1
5 1
5 2

output:

4 2
3 4
1 2
4 5

result:

ok AC

Test #69:

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

input:

5
5 1
3 1
1 2
2 4

output:

2 5
3 2
4 1
4 5

result:

ok AC