QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#110490	#2293. Boredom Buster	zzzYheng	AC ✓	949ms	74296kb	C++14	9.3kb	2023-06-02 16:44:57	2023-06-02 16:45:02

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-02 16:45:02]
评测

测评结果：AC
用时：949ms
内存：74296kb

查看

[2023-06-02 16:44:57]
提交

answer

#include <bits/stdc++.h>

#define Fir first 
#define Sec second

using namespace std; 

const int MaxN = 100005; 

int n; 

struct node {
	int px, py; 
	int vx, vy; 
	
	node(int a = 0, int b = 0, int c = 0, int d = 0) {
		px = a, py = b, vx = c, vy = d; 
	}
}; 

void put(node x) {
	printf("node : px = %d, py = %d, vx = %d, vy = %d\n", x.px, x.py, x.vx, x.vy); 
}

vector<node> vec; 

deque<int> pos[MaxN];  

set<int> set1, set2; 

vector<node> iso; 

vector<int> ans;  

pair<int, int> revealCards(int x, int y) {
	cout << "? " << x << ' ' << y << endl;
	int u, v;
	cin >> u >> v;
	return {u, v};
}
	
void solve1(node x, int px, int py) {
	// 一个孤点
//	puts("ans: "); 
//	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//	puts(""); 
//	puts("solve1: "); 
//	put(x); 
//	printf("%d %d\n", px, py); 
	pair<int, int> p = revealCards(x.px, px); 
//	printf("p : %d %d\n", p.Fir, p.Sec); 
	if (p.Fir == p.Sec) {
		ans[x.px] = x.vx; 
		ans[x.py] = x.vy; 
	}
	else {
		ans[x.py] = x.vx; ans[px] = 0; 
		//exit(0); 
		solve1(node(x.px, px, x.vx, x.vy), x.py, py); 
	}
}

node solve2(node x, node y) {
	// 两个孤点
//	puts("ans: "); 
//	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//	puts(""); 
//	puts("solve2: "); 
//	put(x), put(y); 
	pair<int, int> p = revealCards(x.px, y.px); 
//	printf("p : %d %d\n", p.Fir, p.Sec); 
	if (x.vx == p.Fir || x.vx == p.Sec) ans[x.py] = x.vy; 
	else ans[x.py] = x.vx; 
	if (y.vx == p.Fir || y.vx == p.Sec) ans[y.py] = y.vy; 
	else ans[y.py] = y.vx; 
	return node(x.px, y.px, p.Fir, p.Sec); 
}

void solve3(int id) {
	// 一个自环
	ans[vec[id].px] = ans[vec[id].py] = vec[id].vx; 
	set2.erase(vec[id].vx); 
	pos[vec[id].vx].clear(); 
}

void solve4(node x, node y) {
	// 两点孤链
//	puts("solve 4:"); 
//	put(x); 
//	put(y); 
	pair<int, int> p = revealCards(x.px, y.px); 
//	printf("p: %d %d\n", p.Fir, p.Sec); 
	if (p.Fir == p.Sec) {
		ans[x.px] = p.Fir, ans[y.px] = p.Sec; 
		ans[x.py] = x.vx, ans[y.py] = y.vy; 
	}
	else {
		if (x.vx == p.Fir || x.vx == p.Sec) ans[x.py] = x.vy; 
		else ans[x.py] = x.vx; 
		if (y.vy == p.Fir || y.vy == p.Sec) ans[y.py] = y.vx; 
		else ans[y.py] = y.vy; 
		iso.emplace_back(x.px, y.px, p.Fir, p.Sec); 
	}
	set2.erase(x.vy); 
	set1.erase(x.vx), set1.erase(y.vy); 
} 

void solve5(int id1, int id2) {
	// 链上两点
//	puts("solve 5:"); 
//	put(vec[id1]); 
//	put(vec[id2]); 
	pair<int, int> p = revealCards(vec[id1].px, vec[id2].px); 
	if (p.Fir == p.Sec) {
		ans[vec[id1].px] = ans[vec[id2].px] = p.Fir; 
		ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vy; 
		set1.erase(vec[id1].vx), set2.erase(vec[id2].vy), set1.emplace(vec[id2].vy); 
		set2.erase(p.Fir); 
		pos[p.Fir].clear(); 
		pos[vec[id1].vx].clear(); 
		if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
		else pos[vec[id2].vy].pop_back(); 
	}
	else {
		if (p.Fir == vec[id1].vy || p.Sec == vec[id1].vy) {
			if (p.Fir != vec[id1].vy) swap(p.Fir, p.Sec); 
			if (vec[id1].vx == p.Sec) {
				ans[vec[id1].py] = vec[id1].vy, ans[vec[id2].py] = vec[id2].vy; 
				iso.emplace_back(vec[id1].px, vec[id2].px, vec[id1].vx, vec[id2].vx);
				set1.erase(vec[id1].vx); 
				set2.erase(vec[id1].vy), set2.erase(vec[id2].vy), set1.emplace(vec[id2].vy); 
				pos[vec[id1].vx].clear(); 
				pos[vec[id1].vy].clear(); 
				if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
				else pos[vec[id2].vy].pop_back(); 
			}
			else {
				ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vx; 
				vec[id2].py = vec[id1].px; 
				set1.erase(vec[id1].vx); 
				set2.erase(vec[id1].vy), set1.emplace(vec[id1].vy); 
				pos[vec[id1].vx].clear(); 
				if (pos[vec[id1].vy].front() == id1) pos[vec[id1].vy].pop_front(); 
				else pos[vec[id1].vy].pop_back(); 
			}
		}
		else {
			ans[vec[id1].py] = ans[vec[id2].py] = vec[id1].vy; 
			vec[id2].py = vec[id1].px; 
			vec[id2].vx = vec[id1].vx; 
			set2.erase(vec[id1].vy); 
			pos[vec[id1].vy].clear(); 
			pos[vec[id1].vx].clear(); 
			pos[vec[id1].vx].emplace_back(id2); 
		}
	}
}

void solve6(node x, node y) {
	// 两点孤环
//	puts("solve 6:"); 
//	put(x); 
//	put(y); 
	pair<int, int> p = revealCards(x.px, y.px); 
	if (p.Fir == p.Sec) {
		if (x.vx == p.Fir) {
			ans[x.px] = ans[y.px] = x.vx; 
			ans[x.py] = ans[y.py] = x.vy; 
		}
		else {
			ans[x.px] = ans[y.px] = x.vy; 
			ans[x.py] = ans[y.py] = x.vx; 
		}
		set2.erase(x.vx), set2.erase(x.vy); 
	}
	else {
		solve6(node(x.px, y.px, p.Fir, p.Sec), node(x.py, y.py, p.Fir, p.Sec)); 
	}
}

void solve7(int id1, int id2) {
	// 环上两点
//	puts("solve 7:"); 
//	put(vec[id1]); 
//	put(vec[id2]); 
	swap(vec[id1].vx, vec[id1].vy); 
	pair<int, int> p = revealCards(vec[id1].px, vec[id2].px); 
	if (p.Fir == p.Sec) {
		ans[vec[id1].px] = ans[vec[id2].px] = vec[id1].vy; 
		ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vy; 
		set2.erase(vec[id1].vx), set2.erase(vec[id2].vx), set2.erase(vec[id2].vy); 
		set1.emplace(vec[id1].vx), set1.emplace(vec[id2].vy); 
		pos[vec[id2].vx].clear(); 
		if (pos[vec[id1].vx].front() == id1) pos[vec[id1].vx].pop_front(); 
		else pos[vec[id1].vx].pop_back(); 
		if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
		else pos[vec[id2].vy].pop_back(); 
	}	
	else {
		if (p.Fir == vec[id1].vy || p.Sec == vec[id1].vy) {
			if (p.Fir != vec[id1].vy) swap(p.Fir, p.Sec); 
			if (vec[id1].vx == p.Sec) {
				ans[vec[id1].py] = vec[id1].vy, ans[vec[id2].py] = vec[id2].vy;
				vec[id1].py = vec[id2].px; 
				set2.erase(vec[id2].vx), set1.emplace(vec[id2].vx); 
				set2.erase(vec[id2].vy), set1.emplace(vec[id2].vy); 
				if (pos[vec[id2].vx].front() == id2) pos[vec[id2].vx].pop_front(); 
				else pos[vec[id2].vx].pop_back(); 
				if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
				else pos[vec[id2].vy].pop_back();  
			}
			else {
				ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vx; 
				vec[id2].py = vec[id1].px; 
				set2.erase(vec[id1].vx), set1.emplace(vec[id1].vx); 
				set2.erase(vec[id1].vy), set1.emplace(vec[id1].vy); 
				if (pos[vec[id1].vx].front() == id1) pos[vec[id1].vx].pop_front(); 
				else pos[vec[id1].vx].pop_back(); 
				if (pos[vec[id1].vy].front() == id1) pos[vec[id1].vy].pop_front(); 
				else pos[vec[id1].vy].pop_back();  
			}
		}
		else {
			ans[vec[id1].py] = ans[vec[id2].py] = vec[id1].vy; 
			vec[id2].py = vec[id1].px; 
			vec[id2].vx = vec[id1].vx; 
			set2.erase(vec[id1].vy); 
			pos[vec[id1].vy].clear(); 
			if (pos[vec[id1].vx].front() == id1) pos[vec[id1].vx].pop_front(); 
			else pos[vec[id1].vx].pop_back(); 
			pos[vec[id1].vx].emplace_back(id2); 
		}
	}
}

void init() {
	ans.clear(); 
	vec.clear(); 
	set1.clear(), set2.clear(); 
	for (int i = 1; i <= n / 2; ++i) pos[i].clear(); 
	iso.clear(); 
}

int main() {
	cin >> n; 
	init(); 
	for (int i = 1; i <= n; i += 2) {
		pair<int, int> p = revealCards(i, i + 1); 
		vec.emplace_back(i, i + 1, p.Fir, p.Sec);
		pos[p.Fir].emplace_back(vec.size() - 1); 
		pos[p.Sec].emplace_back(vec.size() - 1);  
	}
	ans.resize(n + 1); 
	for (int i = 1; i <= n / 2; ++i) set2.emplace(i); 
//	for (int i = 0; i < vec.size(); ++i) {
//		printf("id = %d, ", i); 
//		put(vec[i]); 
//	}
//	puts(""); 
	while (set1.size() + set2.size()) {
		//printf("soso %d\n", pos[5][1]); 
//		puts("ans: "); 
//		for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//		puts(""); 
		if (set1.size()) {
			int x = *set1.begin(); 
			int id = pos[x][0]; 
			if (vec[id].vx != x) swap(vec[id].vx, vec[id].vy); 
			if (pos[vec[id].vy].size() == 1) {
//				puts("into iso"); 
//				put(vec[id]); 
				iso.emplace_back(vec[id]); 
				set1.erase(vec[id].vx), set1.erase(vec[id].vy); 
			}
			else {
				if (pos[vec[id].vy][0] != id) swap(pos[vec[id].vy][0], pos[vec[id].vy][1]); 
				int id2 = pos[vec[id].vy][1]; 
				if (vec[id2].vx != vec[id].vy) swap(vec[id2].vx, vec[id2].vy); 
				if (pos[vec[id2].vy].size() == 1) solve4(vec[id], vec[id2]); 
				else solve5(id, id2); 
			}
		}
		else {
			int x = *set2.begin(); 
//			printf("x = %d\n", x); 
			int id1 = pos[x][0], id2 = pos[x][1]; 
//			printf("id = %d, ", id1), put(vec[id1]); 
//			printf("id = %d, ", id2), put(vec[id2]); 
			if (id1 == id2) solve3(id1);
			else {
				if (vec[id1].vx != x) swap(vec[id1].vx, vec[id1].vy); 
				if (vec[id2].vx != x) swap(vec[id2].vx, vec[id2].vy); 
//				printf("id = %d, ", id1), put(vec[id1]); 
//			printf("id = %d, ", id2), put(vec[id2]); 
				if (vec[id1].vy == vec[id2].vy) solve6(vec[id1], vec[id2]); 
				else solve7(id1, id2); 
			}
		}
	}
//	puts("ans: "); 
//	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//	puts(""); 
//	puts("into"); 
//	for (int i = 0; i < iso.size(); ++i) {
//		put(iso[i]); 
//	}
	
	while (iso.size()) {
		if (iso.size() >= 2) {
			node t1 = iso.back(); iso.pop_back(); 
			node t2 = iso.back(); iso.pop_back(); 
			iso.emplace_back(solve2(t1, t2)); 
		}
		else {
			node t = iso.back(); iso.pop_back(); 
			int pos1 = 0, pos2 = 0; 
			for (int i = 1; i <= n; ++i) {
				if (ans[i] == t.vx) pos1 = i; 
				if (ans[i] == t.vy) pos2 = i; 
			}
			solve1(t, pos1, pos2); 
		}
	}
	std::cout << '!';
	for (int i = 0; i < n; ++i) cout << ' ' << ans[i + 1];
	std::cout << std::endl;
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 786ms

memory: 74192kb

input:

100000
14243 13962
6948 22252
19244 19543
38903 11287
38236 8431
8855 44004
32239 28696
4163 13408
34466 26456
34636 16506
17476 19659
41596 45165
44174 8145
32853 13855
13860 32650
39829 40439
26857 16321
28351 11239
14823 35976
18843 47987
13886 18541
1370 15381
16164 41277
10418 10077
1431 40902
...

output:

result:

ok Queries used: 91569

Test #2:

score: 0

Accepted

time: 805ms

memory: 74220kb

input:

100000
41874 17281
40541 23499
2411 12273
46034 10695
9169 29627
12031 28270
45783 2390
6091 49751
46029 45662
38649 48940
33046 6151
33047 4151
26515 11802
35711 9780
39443 38890
10137 3418
14295 6609
22808 1819
30599 9883
31665 21226
25409 49659
7103 4428
12488 49739
24656 47502
13155 33362
23201 ...

output:

result:

ok Queries used: 91586

Test #3:

score: 0

Accepted

time: 777ms

memory: 74288kb

input:

100000
30112 37386
30103 43837
33471 22886
48842 38666
11897 12326
45477 7200
37936 6946
1214 20263
18986 45656
36129 238
23351 21401
28563 46035
40905 22823
49289 30770
1815 28903
9649 45442
5061 15590
10676 11036
26730 36103
9295 887
34883 2485
22795 23512
19692 23191
24958 25290
20334 47633
44705...

output:

result:

ok Queries used: 91665

Test #4:

score: 0

Accepted

time: 735ms

memory: 74180kb

input:

100000
33163 34884
19056 36345
2327 6226
11591 694
39587 36075
2376 32164
47236 24354
36062 18121
28138 25306
35217 34927
6254 3337
3343 20579
49389 10923
6723 12595
23906 43722
34034 20651
30515 32147
1408 30181
38711 24255
32341 34078
11299 31963
10609 18470
34352 17418
748 16813
1041 27156
37969 ...

output:

result:

ok Queries used: 91558

Test #5:

score: 0

Accepted

time: 900ms

memory: 74184kb

input:

100000
40937 4070
22563 46970
15015 19983
21041 27880
9702 46006
8342 13805
1775 43023
13484 18867
14638 29434
19550 10188
36435 5572
49841 13391
12427 11697
44145 43205
41631 25796
43402 2823
41805 21667
37979 6648
29640 25960
2009 44912
18453 8798
35990 17423
6613 23017
25369 30982
8851 42608
7082...

output:

result:

ok Queries used: 91682

Test #6:

score: 0

Accepted

time: 795ms

memory: 74192kb

input:

100000
1130 31884
49308 48754
6055 16268
48914 6837
21607 25436
46310 20880
37134 20192
23103 48856
3714 2717
16306 34785
3547 48953
37342 39819
18169 34110
19040 42695
15214 41406
6104 44116
32983 46252
5397 30836
33083 5489
29799 40374
30528 30997
8870 24482
16270 2734
43978 33301
48784 46823
3797...

output:

result:

ok Queries used: 91604

Test #7:

score: 0

Accepted

time: 741ms

memory: 74220kb

input:

100000
5399 40784
18950 32985
22398 28650
24903 28512
4256 46620
27350 19938
12425 39238
24879 4421
43792 24236
12415 2689
33979 21386
30980 49567
39120 21224
42185 7074
28206 21035
42130 44199
27572 36638
21956 12027
1083 37731
38147 34517
18128 28172
17761 13123
35166 26156
1511 28749
9093 8086
37...

output:

result:

ok Queries used: 91786

Test #8:

score: 0

Accepted

time: 708ms

memory: 74188kb

input:

100000
40909 1756
44404 31048
24079 3219
4283 29950
45328 46197
3684 17379
21098 5416
36281 21927
26750 22535
5277 36018
9754 8231
18439 25845
37927 38238
16719 14083
39791 4261
32700 46123
7282 35522
46060 37495
29786 22237
13347 28386
49318 2404
20523 37853
33289 28048
20142 44824
14713 14910
3293...

output:

result:

ok Queries used: 91554

Test #9:

score: 0

Accepted

time: 897ms

memory: 74200kb

input:

100000
35293 45757
6191 26468
41683 44654
37953 35699
3296 36472
3983 12011
10427 3746
4160 26216
22617 5186
13109 40777
8963 48088
23728 28240
2042 492
18794 1682
39209 46769
1996 9365
32135 13210
43688 21484
31666 7533
15173 19652
6456 7209
38348 17827
11884 12850
30954 31373
28185 11276
14700 372...

output:

result:

ok Queries used: 91558

Test #10:

score: 0

Accepted

time: 786ms

memory: 74276kb

input:

100000
24884 49809
40938 5417
12327 22989
42861 3582
22041 40882
47489 28665
32672 16836
22056 24127
30104 5856
243 2845
31960 25631
22190 34523
24587 3063
16983 6861
395 3874
5240 5463
17796 3605
1419 19261
32860 467
7054 38677
11504 6061
39858 8551
421 26993
28287 13592
41526 39515
33588 17898
361...

output:

result:

ok Queries used: 91711

Test #11:

score: 0

Accepted

time: 799ms

memory: 74188kb

input:

100000
14224 2032
11952 26955
19346 8413
46354 1665
45235 12116
43886 1777
37062 30235
4733 30364
1263 32605
47328 15966
19660 48228
13534 13032
41745 49948
42765 8618
46383 38917
5814 9939
8960 38408
40962 10072
27944 37952
38803 5967
15171 43555
14998 8547
33742 17014
43461 40210
2319 10076
9540 1...

output:

result:

ok Queries used: 91715

Test #12:

score: 0

Accepted

time: 712ms

memory: 74196kb

input:

100000
27604 32149
12635 24383
41814 36647
39816 25454
36866 8730
39450 4708
13155 11827
37754 31496
23706 23500
46403 4495
45000 46442
30715 48094
29906 38682
43980 33820
41258 43556
15047 18034
17236 2019
49638 27425
46644 35617
33834 1523
6544 7531
22825 25458
3554 34174
19911 47873
8826 49101
13...

output:

result:

ok Queries used: 91651

Test #13:

score: 0

Accepted

time: 830ms

memory: 74220kb

input:

100000
8758 27484
33718 40042
1398 40370
18366 9743
32429 31502
46054 20536
340 35579
10556 17404
6369 12858
32757 39680
49028 26362
1414 24718
9301 8087
15011 42973
19773 12681
9702 8043
29229 29547
26429 18322
12387 6402
26187 49049
45736 26512
22173 36541
848 19166
7809 11487
45899 38485
42783 16...

output:

result:

ok Queries used: 91806

Test #14:

score: 0

Accepted

time: 810ms

memory: 74188kb

input:

100000
19864 26920
44089 42692
49629 42912
39354 1283
26110 32591
10090 48497
16197 4600
46287 43356
29677 43252
31443 1924
15263 15782
2954 45760
10418 8639
43599 10564
30502 43359
13189 14540
35859 46268
43103 13459
8460 47138
3803 10120
32705 19486
49479 29906
8997 1754
8981 49432
38207 3617
1550...

output:

result:

ok Queries used: 91647

Test #15:

score: 0

Accepted

time: 914ms

memory: 73940kb

input:

100000
15814 46809
20064 41411
29396 380
14209 568
44566 25368
36637 30211
48994 42636
28257 19352
17317 47815
32873 11951
10111 36061
4056 47603
31048 26045
23630 32704
15218 41506
9843 18711
43220 15263
45339 43682
23356 29953
36486 44831
37448 35129
16347 5997
5166 27806
5437 18734
8405 31798
442...

output:

result:

ok Queries used: 91593

Test #16:

score: 0

Accepted

time: 857ms

memory: 74272kb

input:

100000
25115 23788
17360 27071
39312 7931
18882 48035
26611 40933
20844 7625
36468 16970
28395 41599
44549 41638
26433 11360
25505 11289
26232 41080
27984 9708
3586 19110
49363 3945
21080 13585
47475 37525
7437 39051
40109 47745
9174 49301
4801 12485
7755 26277
45866 38172
12325 13352
42452 33800
47...

output:

result:

ok Queries used: 91614

Test #17:

score: 0

Accepted

time: 851ms

memory: 74188kb

input:

100000
4800 44464
29843 41843
3962 18915
17712 40131
24999 16975
30349 4171
22867 10069
5882 8387
7475 36163
17571 28224
16376 43350
35755 38157
26635 41300
41228 18665
7535 27142
43410 37503
28668 9795
10964 1050
40352 24177
3237 37759
41774 44141
21113 28545
10212 22527
2633 6737
18415 13695
3163 ...

output:

result:

ok Queries used: 91674

Test #18:

score: 0

Accepted

time: 805ms

memory: 74216kb

input:

100000
44631 36858
27730 27812
51 40032
43835 5028
44463 44059
499 37895
28794 412
29060 40118
27263 43167
41888 5875
30878 35105
21220 24313
27192 31097
37325 24840
25861 25739
21256 46083
45963 8605
35290 29874
23572 409
16904 8287
23620 49165
9973 40872
24932 41531
2230 8387
11491 8519
815 14313
...

output:

result:

ok Queries used: 91662

Test #19:

score: 0

Accepted

time: 738ms

memory: 74224kb

input:

100000
33878 5878
33163 9511
12095 48704
44083 16918
9905 18415
12399 39228
43802 20957
24565 22203
42532 12745
35151 40514
31302 28809
4955 9393
15057 5675
37095 24525
24738 8574
9506 19124
22073 15239
20620 44921
29010 43772
20144 42842
44398 38768
41938 30444
44599 29016
35663 41569
1727 3685
671...

output:

result:

ok Queries used: 91659

Test #20:

score: 0

Accepted

time: 829ms

memory: 74236kb

input:

100000
32450 20712
19702 27741
44996 31088
35631 40877
20708 11657
15775 31631
13855 5413
48924 25514
33872 3065
31825 4511
44416 21123
45027 46776
16005 4734
23615 26598
20508 8439
35188 14986
11814 14060
45750 36807
26272 35185
19725 38914
21989 32032
14781 49960
11164 41115
815 32926
27610 4262
4...

output:

result:

ok Queries used: 91675

Test #21:

score: 0

Accepted

time: 810ms

memory: 74272kb

input:

100000
14733 37470
30892 41165
16234 4184
8806 2532
29005 20091
6461 11499
207 6219
2442 11537
44449 18067
6627 29832
40577 13920
5040 13089
31871 40905
29403 9337
29170 42003
38519 29307
38561 21232
7807 25977
33909 702
47092 28807
36353 9433
22364 17834
25592 38719
36131 46401
44840 1003
22154 426...

output:

result:

ok Queries used: 91670

Test #22:

score: 0

Accepted

time: 704ms

memory: 74188kb

input:

100000
10727 43010
13580 34849
8478 19355
1122 49557
1415 22809
44705 43850
44054 19962
13855 4894
13589 25201
18967 17143
38922 9233
11051 32528
35784 40194
7854 13005
34054 18438
29848 31322
48259 41838
9656 20266
17981 49522
28056 39156
31351 12891
48597 15833
41512 1948
44096 20738
47480 15439
1...

output:

result:

ok Queries used: 91686

Test #23:

score: 0

Accepted

time: 776ms

memory: 74220kb

input:

100000
2269 4805
3694 22860
25339 20821
16343 44889
27992 308
40796 40282
22792 6978
30127 41373
39903 10489
17499 31631
2283 16861
41045 49226
29003 45764
4017 24613
26178 40704
7012 31691
864 6093
9264 29223
32485 5186
43490 47209
19406 46688
29556 27657
9949 2115
46245 18431
6487 4100
1046 42118
...

output:

result:

ok Queries used: 91521

Test #24:

score: 0

Accepted

time: 897ms

memory: 74220kb

input:

100000
16807 23699
48983 7450
36833 35846
6575 29615
40616 37200
15420 19465
28876 25080
410 35877
20147 17159
23983 17997
30140 42128
35076 43754
41071 39942
32751 47337
25680 45878
2055 7201
24559 46504
9214 26886
8191 18575
6941 49775
25178 18897
21335 13720
4818 31053
29425 23963
33613 6803
1784...

output:

result:

ok Queries used: 91645

Test #25:

score: 0

Accepted

time: 797ms

memory: 74228kb

input:

100000
16990 22536
7635 39951
8759 23730
34430 17303
14574 39629
17896 12215
44973 22345
7838 889
27174 47825
11874 8526
33449 31250
23402 32115
6604 16833
13719 18874
11797 46958
23916 19410
18359 11490
38279 35374
31706 46653
41474 16151
29475 42233
737 39458
45016 49872
49159 12255
47964 29016
21...

output:

result:

ok Queries used: 91614

Test #26:

score: 0

Accepted

time: 776ms

memory: 74192kb

input:

100000
3866 39743
39285 42958
41298 21702
46774 40413
33076 38505
29876 18199
7264 30577
7309 45248
48058 29988
46660 41702
7724 5827
39691 35745
789 13424
24951 27059
48919 18818
12432 6441
16036 41129
35232 20745
11703 32027
41214 7879
46227 49211
35393 14552
30331 21063
22288 8516
32600 40156
558...

output:

result:

ok Queries used: 91718

Test #27:

score: 0

Accepted

time: 763ms

memory: 74188kb

input:

100000
37746 36784
31470 35665
18408 460
12212 29981
13491 7079
29397 17478
2988 11773
37339 15987
19752 43263
42010 25603
32342 893
49094 9744
20892 2889
30669 40646
39848 22885
35938 24897
7132 11440
11371 6452
3736 41761
5107 17543
29930 35628
13030 10536
43465 19306
41286 33025
39057 24586
26325...

output:

result:

ok Queries used: 91545

Test #28:

score: 0

Accepted

time: 739ms

memory: 74224kb

input:

100000
40701 37047
33033 15930
31785 24681
28389 29799
44323 28565
11406 31410
11188 38261
40043 44777
41860 7258
8036 2340
42272 3421
29591 3937
37129 38379
39948 18649
48362 22322
37645 18647
33424 23291
28916 17002
8936 14743
38051 2436
49659 3166
47897 29568
17 47865
7647 47595
32605 30222
11621...

output:

result:

ok Queries used: 91712

Test #29:

score: 0

Accepted

time: 709ms

memory: 74220kb

input:

100000
33580 19207
22198 34599
23681 35433
12385 13315
26232 16107
15188 40085
42436 27160
42468 4300
39629 10235
10734 33101
43612 5025
41695 36136
36142 26094
1633 38468
24130 33215
12516 46150
45179 32636
23915 47649
39272 43871
7451 48784
4396 43796
43745 9282
36287 19214
8292 39834
8083 45107
4...

output:

result:

ok Queries used: 91649

Test #30:

score: 0

Accepted

time: 691ms

memory: 74192kb

input:

100000
34872 24816
29320 6372
34315 16365
19105 3898
31679 2731
9827 39402
1359 8439
46238 32740
47090 6010
15611 24658
21848 26248
21139 5331
6848 30616
25710 37059
22419 15131
46188 31276
29137 18370
2336 21001
11041 41868
32338 27487
39531 48938
12197 7289
30016 4232
2212 1735
30525 26454
17459 1...

output:

result:

ok Queries used: 91729

Test #31:

score: 0

Accepted

time: 782ms

memory: 74272kb

input:

100000
14319 38890
24030 8230
15150 7256
11280 12423
11441 9806
28869 31854
10259 11716
8847 37653
26054 29008
30601 27832
13311 42704
21845 1254
9545 29933
5837 30893
32755 36037
6732 9780
13061 46324
15369 6035
43832 45615
12251 45494
39864 49826
42342 8077
47178 31721
40761 4375
25407 11864
44847...

output:

result:

ok Queries used: 91583

Test #32:

score: 0

Accepted

time: 839ms

memory: 74168kb

input:

100000
15596 31793
5616 8996
33624 6413
15658 18539
36244 5786
18510 49827
26768 18823
48276 35545
27703 41900
45525 26880
7899 38887
1722 24905
4895 34374
40988 35585
3848 7545
43854 3721
47374 44128
17541 1255
42172 26184
17125 45103
43671 29334
44560 415
10355 24075
17835 18826
41660 48229
18108 ...

output:

result:

ok Queries used: 91504

Test #33:

score: 0

Accepted

time: 717ms

memory: 74180kb

input:

100000
19399 34245
32276 14533
48882 1164
42324 40483
27237 34287
34863 39892
36744 20171
40486 31305
18908 22657
36595 13697
18641 26464
22074 1270
16692 34658
33116 24228
45593 29300
8884 29872
6124 44969
35930 2856
18428 12369
41483 13325
2889 49279
31423 43800
31219 5095
8044 10050
7669 2463
147...

output:

result:

ok Queries used: 91729

Test #34:

score: 0

Accepted

time: 833ms

memory: 74192kb

input:

100000
9353 13775
23352 11236
891 3576
28015 21973
43911 18818
29232 16715
11024 6641
41930 31361
5968 44772
5845 748
47510 22688
5215 33869
18375 45464
12038 16696
33263 3884
32570 5114
44115 34501
49775 36998
39050 18340
46995 5008
40451 40535
15843 43451
40461 29738
33535 29996
47260 26791
23277 ...

output:

result:

ok Queries used: 91740

Test #35:

score: 0

Accepted

time: 825ms

memory: 74180kb

input:

100000
17636 48369
33902 21193
19244 2679
29393 21948
21887 28052
5511 41608
40150 23307
43618 16709
42685 39956
45840 598
48485 146
44289 22892
40478 34530
17821 21274
27834 35625
26536 19197
17495 12787
1098 19026
11610 12435
33732 30052
3101 43112
44622 47708
23488 20198
28081 4601
12832 23531
36...

output:

result:

ok Queries used: 91652

Test #36:

score: 0

Accepted

time: 779ms

memory: 74236kb

input:

100000
41899 22104
42915 1950
43781 41930
5993 18626
22231 44754
38595 6973
25412 9925
3598 28151
38821 11702
18796 6970
6747 20814
29381 5137
35093 15921
34345 47285
16277 28907
43093 16733
21690 29238
31904 13413
16051 9319
12216 2008
15559 28240
39489 43751
11265 33400
32640 38965
6085 8075
17671...

output:

result:

ok Queries used: 91665

Test #37:

score: 0

Accepted

time: 672ms

memory: 74200kb

input:

100000
34378 43363
20286 9772
4710 35210
9990 10117
24281 7238
33043 28523
24706 40329
42372 29676
45091 13124
35349 18178
32102 10517
39891 28574
35999 34698
16849 49734
16129 26031
1291 38734
43365 23169
45721 24413
32744 6002
38103 15866
31849 48978
42440 35712
4319 38668
35926 16194
44952 22585
...

output:

result:

ok Queries used: 91684

Test #38:

score: 0

Accepted

time: 788ms

memory: 74212kb

input:

100000
3619 7932
40794 40947
41053 33534
19371 28
12684 36996
7320 27097
5713 30500
1315 31380
46772 41545
7175 33153
33658 38123
8373 49455
12887 14292
49959 25573
26230 2749
23370 17238
44800 32750
25728 38162
2771 48113
16903 4786
37353 911
12158 10309
13663 25725
2319 37812
18685 19068
29507 260...

output:

result:

ok Queries used: 91711

Test #39:

score: 0

Accepted

time: 801ms

memory: 74272kb

input:

100000
10414 24191
17764 19843
20067 23579
9837 36924
36442 9652
44339 18884
10761 34561
33663 36241
42337 2829
36775 37710
30032 16
10129 29241
6985 36684
13173 41892
1954 28782
4089 48076
22103 54
25712 18426
14681 43196
47892 41298
28442 31581
33481 6310
43244 45479
22214 642
25278 22562
35682 24...

output:

result:

ok Queries used: 91807

Test #40:

score: 0

Accepted

time: 774ms

memory: 74288kb

input:

100000
7264 49830
413 39803
43109 25227
48122 1417
22744 10408
33363 46696
32791 12406
28980 29403
26377 35595
12971 47774
8823 34178
37406 19779
41368 31760
30454 26899
49895 39745
22922 2284
23043 29293
37667 11755
13093 30189
45452 11832
39007 21884
36280 41503
45378 5995
1170 11234
10843 5145
24...

output:

result:

ok Queries used: 91788

Test #41:

score: 0

Accepted

time: 822ms

memory: 74276kb

input:

100000
13348 12101
14119 5627
34947 33871
24912 2238
42789 15377
6651 3404
31546 49064
32678 5033
5 45180
42578 20565
26431 40744
20547 32805
18560 49205
14041 28469
41971 16189
49600 45371
25468 45843
11567 1268
25139 37790
46608 43008
1983 49127
479 28766
18961 27589
42753 28873
21224 9063
24196 3...

output:

result:

ok Queries used: 91745

Test #42:

score: 0

Accepted

time: 781ms

memory: 73992kb

input:

100000
5172 16601
19653 8339
46095 514
21858 33622
31901 27448
7408 42090
5736 48546
42524 25797
589 48594
20689 41736
2757 46185
21271 29583
21872 43839
25227 27811
16398 24763
38525 48111
20934 10117
43733 44480
13779 32757
42093 25427
35301 47656
20249 41922
2497 18045
31402 18978
48312 26048
333...

output:

result:

ok Queries used: 91581

Test #43:

score: 0

Accepted

time: 775ms

memory: 74224kb

input:

100000
30895 24355
24849 10362
41489 22668
7330 39618
34079 41819
31724 42527
28317 32562
10974 9661
18120 10133
22057 597
40204 30039
11877 47184
49234 12017
47893 35631
17545 33743
49768 35145
3022 10
9016 5719
46747 44908
28676 4097
27712 2123
21604 20270
19912 24873
5040 45738
36644 45147
46194 ...

output:

result:

ok Queries used: 91681

Test #44:

score: 0

Accepted

time: 784ms

memory: 74192kb

input:

100000
35822 12236
21172 36906
3323 721
8896 31333
2759 23076
6816 23575
7532 29227
7943 14688
47928 26432
32161 28685
10231 46716
40040 29352
13600 12703
12480 37617
32358 27099
10533 32246
16008 49703
34669 49530
25614 25810
38855 34882
33525 34191
13270 11542
6842 34783
16381 46296
49800 11589
51...

output:

result:

ok Queries used: 91704

Test #45:

score: 0

Accepted

time: 815ms

memory: 74220kb

input:

100000
13876 48438
15033 10824
14117 34490
24953 38658
35409 34592
44545 42262
39091 9542
25911 9352
10981 15748
18641 2258
33799 34502
8758 32016
17702 2673
4951 13033
32669 30276
15948 15998
9649 40849
4149 22448
33831 45879
20651 15937
15696 13845
14745 469
20065 4820
33827 45611
42667 44403
2081...

output:

result:

ok Queries used: 91729

Test #46:

score: 0

Accepted

time: 724ms

memory: 74184kb

input:

100000
39301 7654
35111 33606
6679 17581
6382 6197
18185 19141
19606 48638
20683 25902
28882 40924
17967 28475
14274 8891
27549 41909
24894 7326
15193 31230
23506 33289
26205 45462
15758 745
49659 24879
31794 2220
45658 3701
13905 33482
6227 1593
7392 38427
40760 48126
19547 45525
28418 26637
34115 ...

output:

result:

ok Queries used: 91624

Test #47:

score: 0

Accepted

time: 813ms

memory: 74292kb

input:

100000
16465 18256
15583 34003
5969 44111
49811 34146
192 33890
40830 6076
22323 28574
40297 23455
27009 19729
31559 8363
1733 24612
25635 27716
20307 16171
17732 48331
17762 2626
26953 327
34568 13953
4999 9713
29522 16431
1812 1261
41375 7667
31859 28852
33168 34127
41537 6440
13785 47144
40194 96...

output:

result:

ok Queries used: 91649

Test #48:

score: 0

Accepted

time: 785ms

memory: 74192kb

input:

100000
1096 20859
17041 8365
33471 6338
15802 48219
15608 47578
39320 3006
32231 44202
46353 3512
48987 24855
1752 10407
32653 48264
47240 5121
25901 44278
49483 43103
41896 7798
8335 21824
45721 29942
14007 11667
29926 40339
25060 29048
36979 32032
41557 3404
20531 522
46296 40712
32467 13155
7383 ...

output:

result:

ok Queries used: 91574

Test #49:

score: 0

Accepted

time: 775ms

memory: 74296kb

input:

100000
22670 29187
6537 23663
14005 35942
23619 16396
2189 41180
35242 9262
28676 14785
19027 22457
40513 16868
27804 45029
26491 96
30873 13614
26137 30345
39568 15207
19048 5662
32308 22169
27373 15251
25541 30520
44972 43601
16901 19875
25914 35609
36638 37457
46539 27946
45458 8378
31814 43596
4...

output:

result:

ok Queries used: 91699

Test #50:

score: 0

Accepted

time: 808ms

memory: 74272kb

input:

100000
32392 43666
31023 20255
31924 26023
19208 19600
5309 41809
39940 8475
40883 24159
48799 25187
42742 8296
13860 33225
16677 21210
47142 25084
828 21977
33299 36421
22995 24680
23139 37276
47736 2146
4956 37154
34627 40417
10076 37801
37202 47920
11296 29179
9231 24153
4367 30395
36952 21835
28...

output:

result:

ok Queries used: 91605

Test #51:

score: 0

Accepted

time: 828ms

memory: 74272kb

input:

100000
31954 15177
22178 43050
36094 4583
7495 689
5958 8197
9843 19904
30847 48150
10045 36341
43116 47140
8205 20069
2862 1428
45736 34010
44440 19541
11193 19446
15141 21483
45602 37182
15797 8663
30381 13144
43172 16453
17802 28719
9966 25886
29657 16948
40885 23953
3877 16633
14905 7681
36874 3...

output:

result:

ok Queries used: 91766

Test #52:

score: 0

Accepted

time: 848ms

memory: 74224kb

input:

100000
9777 46682
34667 16743
23699 17281
47179 37719
42760 33178
30911 12680
3550 49831
14259 12768
38948 7807
41922 35032
13273 41909
45982 47490
17699 44330
30073 41514
10998 35256
45105 9505
30330 14860
20367 4603
4695 3706
45410 27907
40535 17689
40245 21732
22332 42171
12610 8168
4242 18313
30...

output:

result:

ok Queries used: 91694

Test #53:

score: 0

Accepted

time: 764ms

memory: 74232kb

input:

100000
49494 45787
11864 46891
37424 14893
45140 639
9300 29275
2521 43764
3697 21294
22764 17737
49772 4725
29481 25596
1169 44131
25920 28028
9870 18241
921 29172
26229 30982
43077 39935
19385 9111
10957 43652
9142 683
17571 30473
14782 12468
15307 16375
8172 24293
24556 7151
29494 11644
19409 156...

output:

result:

ok Queries used: 91655

Test #54:

score: 0

Accepted

time: 722ms

memory: 74256kb

input:

100000
41851 40791
12817 9621
20975 37017
7007 29434
39297 32300
13434 30995
9773 37093
21757 27367
15508 21497
23203 11870
48724 9356
45342 22403
31352 34184
42994 20144
44497 33430
10582 8825
17460 14326
31795 1785
46845 18909
38592 3386
5427 47603
12889 21800
19670 20888
42239 44371
5884 32529
34...

output:

result:

ok Queries used: 91692

Test #55:

score: 0

Accepted

time: 949ms

memory: 74188kb

input:

100000
31296 43873
43481 43731
32508 9468
31654 5024
23295 44486
26739 13360
2076 10450
2208 40335
4595 49700
32791 8111
46907 16855
18092 2627
14796 36686
110 26172
19583 3634
36596 38182
37057 13807
46752 30780
8289 9989
44335 8509
10917 10447
24220 27587
24875 36011
34269 15905
47067 35695
9142 4...

output:

result:

ok Queries used: 91609

Test #56:

score: 0

Accepted

time: 758ms

memory: 74192kb

input:

100000
4630 3334
4749 33290
34191 40651
17370 24146
22730 1667
31363 36015
29935 1341
31378 29912
15317 34133
31839 23141
48999 39039
5296 35188
15248 26048
24447 171
12422 31439
41806 37518
49110 25028
23349 6495
44880 12375
16934 31137
3228 31643
1942 38633
5376 48703
28686 16741
16631 26789
43424...

output:

result:

ok Queries used: 91649

Test #57:

score: 0

Accepted

time: 764ms

memory: 74192kb

input:

100000
48586 33625
47362 47993
46398 43568
11940 1046
44974 46387
711 49952
5592 25808
15733 16665
12990 49745
23746 8114
48404 41662
420 49149
40006 21469
26612 46155
7361 9466
21946 48607
18714 32145
27695 34768
48387 28311
15440 7075
31520 20277
43212 2707
14058 23188
2482 21906
42984 18616
46262...

output:

result:

ok Queries used: 91662

Test #58:

score: 0

Accepted

time: 841ms

memory: 74216kb

input:

100000
39479 24232
17377 509
27830 20970
36190 13120
14792 12612
5565 20979
43615 13547
46878 26353
48209 23991
18597 1480
46666 12938
18408 9359
2131 5528
20852 20202
44097 23081
39064 15745
24027 31783
45324 33226
33202 1702
28595 12313
11261 5879
7065 46443
21347 45419
15525 11179
14983 22152
350...

output:

result:

ok Queries used: 91609

Test #59:

score: 0

Accepted

time: 619ms

memory: 74188kb

input:

100000
5376 49909
41082 6671
34705 24036
23006 17116
35673 20920
28108 22414
28504 47335
5209 47911
37789 47268
35469 22281
23195 45697
413 20791
29424 46712
40795 34419
41488 20600
36799 48752
37289 6875
30222 33492
36628 35866
25150 28650
22585 36161
15887 3265
14168 6316
2598 40923
43264 41382
47...

output:

result:

ok Queries used: 91656

Test #60:

score: 0

Accepted

time: 767ms

memory: 74204kb

input:

100000
35122 47184
5397 32069
6615 48520
4213 25297
31789 29745
34734 39517
49096 12951
18574 27702
26665 47577
10717 37904
33229 42274
454 1448
42983 23964
32969 12092
42898 20278
14624 41353
15493 3001
19970 29808
36616 19335
17787 18455
24067 46714
26703 19594
2401 41378
20156 11443
27692 37911
4...

output:

result:

ok Queries used: 91617

Test #61:

score: 0

Accepted

time: 789ms

memory: 74196kb

input:

100000
2910 18415
29043 37586
1478 28750
42615 46932
28268 11552
28421 11499
12287 10831
49652 11431
39052 36212
29198 24282
40205 43085
8874 10495
32639 37911
45511 22277
23365 45932
24751 37356
33475 3764
20510 31404
28960 2713
16101 23472
12923 12503
5613 19990
49563 45365
17089 10084
36718 36735...

output:

result:

ok Queries used: 91571

Test #62:

score: 0

Accepted

time: 777ms

memory: 74272kb

input:

100000
43608 13332
38716 24575
1878 44188
6009 47316
41547 37749
12534 1236
42791 21460
23040 41756
40322 14650
38670 10037
25641 34966
11939 9288
49661 28120
48173 42519
44252 18791
8895 11678
7272 22903
24452 1670
26849 24512
24231 13217
33363 29903
13135 10086
16091 30335
48751 49238
38866 48400
...

output:

result:

ok Queries used: 91688

Test #63:

score: 0

Accepted

time: 783ms

memory: 74224kb

input:

100000
45908 2674
44890 11389
27090 45410
13841 15656
24699 39770
46834 417
13757 25468
38482 43314
2295 9054
33406 23923
24681 46794
30126 7129
48246 5259
15052 5972
21114 21671
13981 23493
20076 19703
36465 1781
30704 22894
15651 33771
38538 45626
10864 25169
19182 18543
31826 5511
35367 37075
346...

output:

result:

ok Queries used: 91637

Test #64:

score: 0

Accepted

time: 896ms

memory: 74180kb

input:

100000
1123 43472
37152 22248
518 20832
44863 24745
35800 9489
8977 24181
44349 17723
19344 26675
49620 40179
29801 48906
46980 16556
43130 32009
35752 5294
7053 6427
7114 30232
44776 39698
37006 46740
5516 36210
19685 5979
49522 21276
48154 16628
18711 42757
3454 32037
12415 11827
10813 1672
35883 ...

output:

result:

ok Queries used: 91596

Test #65:

score: 0

Accepted

time: 688ms

memory: 74260kb

input:

100000
41380 2361
40733 9923
27427 4378
41421 12434
20755 22888
4042 49239
39984 7503
42375 47089
38226 28619
20325 15258
288 32300
29784 42471
25348 42739
45039 33234
25603 43309
7083 28323
21645 33796
18703 6055
38471 45418
32608 30494
47569 6976
16704 7213
31457 8147
6560 15457
30621 10674
1688 4...

output:

result:

ok Queries used: 91759

Test #66:

score: 0

Accepted

time: 752ms

memory: 74268kb

input:

100000
10547 164
47888 2382
2427 3040
8128 29222
7451 44721
24689 12919
29831 42312
34265 39161
25720 29581
35341 41759
28927 19916
1713 33709
38600 27223
25066 8389
7725 41317
44657 12963
30550 3582
45663 23368
44620 47084
20334 30284
36439 28785
11749 28720
20324 39939
42070 26394
47326 17489
1607...

output:

result:

ok Queries used: 91707

Test #67:

score: 0

Accepted

time: 747ms

memory: 74188kb

input:

100000
19005 13883
1700 4080
12928 43031
26391 14645
14085 34124
30454 49237
16476 47564
4473 48370
8612 45346
49260 7507
11412 2811
49626 37469
47062 44049
34266 3182
31073 38516
10817 37062
49631 21985
4728 32912
47518 1825
13814 6043
14914 40315
16471 21654
37044 39923
17849 33295
30081 16189
436...

output:

result:

ok Queries used: 91624

Test #68:

score: 0

Accepted

time: 879ms

memory: 74200kb

input:

100000
27473 45007
28085 14681
32829 49110
41174 42269
34974 34673
31673 25354
49007 28163
49143 36470
15752 18218
12911 35707
44159 30347
46238 9447
45245 28412
4678 24210
28781 19073
31457 44417
3983 28587
36251 7100
4659 40698
21776 2102
5626 22890
40559 30524
7115 12932
31262 32744
9030 36188
43...

output:

result:

ok Queries used: 91684

Test #69:

score: 0

Accepted

time: 707ms

memory: 73924kb

input:

100000
9561 44805
28755 1157
35157 44637
14279 8052
38441 34403
44360 48083
19306 40007
5491 31149
16773 10552
358 5256
17482 7133
31850 32358
33849 15925
42053 18995
25319 30794
21803 24338
29638 39507
7934 34126
17398 2636
48814 25979
32880 5887
44526 25648
20220 7629
37481 42995
33690 19472
8901 ...

output:

result:

ok Queries used: 91548

Test #70:

score: 0

Accepted

time: 764ms

memory: 74252kb

input:

100000
38609 21751
49 3316
22718 16723
37163 32419
40083 38975
33766 26325
48477 27623
30443 4845
18852 2167
45473 11396
32837 14278
49770 14039
33918 30053
26577 18055
37625 31594
11491 20798
39082 44764
33898 25393
22931 9840
48663 25637
85 6223
8336 28128
11520 40470
37849 12591
16985 23713
9204 ...

output:

result:

ok Queries used: 91640

Test #71:

score: 0

Accepted

time: 670ms

memory: 74008kb

input:

100000
17307 4161
4287 15204
45874 13913
9672 7354
34779 33417
22119 44069
10476 28769
11544 11240
49418 20225
9204 34232
6737 48965
30211 23126
44273 33190
1373 29255
7355 33336
6667 42400
35894 29782
44457 31982
39997 13438
36167 3924
30331 34023
9528 29511
13572 45461
8067 34529
21454 40909
21594...

output:

result:

ok Queries used: 91558

Test #72:

score: 0

Accepted

time: 761ms

memory: 74256kb

input:

100000
22470 4401
17967 14245
11622 3633
22899 19666
13869 11248
12220 18911
27848 23074
21693 22532
18468 14868
27512 32774
6749 39027
6272 25239
33331 15630
9842 14617
49106 24361
3776 32802
21416 25580
35391 15489
17081 32029
12459 34631
15321 45611
19077 12997
15680 49434
48677 47027
16655 1165
...

output:

result:

ok Queries used: 91704

Test #73:

score: 0

Accepted

time: 775ms

memory: 74180kb

input:

100000
49582 18883
30237 49784
45810 45583
5171 35832
2867 22917
10200 46843
26383 35802
28771 2753
41431 39309
11226 4247
22347 14196
37566 38153
41794 33990
16189 7140
28884 12604
14602 16308
16709 8754
15082 10276
39060 5461
43233 29582
30789 42913
22009 43626
38718 14722
41438 39620
5522 12581
1...

output:

result:

ok Queries used: 91688

Test #74:

score: 0

Accepted

time: 775ms

memory: 74188kb

input:

100000
25739 32020
4348 27643
22257 45780
3078 7435
16553 47483
8799 9294
3118 24028
15577 11914
30553 42097
37234 4133
24444 14749
24634 29499
7346 35159
2737 1988
27321 4542
1832 27466
31019 28548
6212 21820
7439 17653
28849 46944
35010 44765
25407 39574
16599 14309
45877 41600
11827 28788
18738 2...

output:

result:

ok Queries used: 91736

Test #75:

score: 0

Accepted

time: 936ms

memory: 74216kb

input:

100000
40661 13567
47881 25287
39999 2066
23695 16341
39513 4998
34991 18538
37828 7185
49631 3617
31634 11710
22355 5095
13675 48943
42140 11904
9766 1060
25083 32944
34482 41534
16671 5515
44464 11069
22760 49573
26010 13569
46796 7740
13957 46778
7669 44664
35721 44853
30540 29984
49054 49205
399...

output:

result:

ok Queries used: 91647

Test #76:

score: 0

Accepted

time: 854ms

memory: 74236kb

input:

100000
22419 35976
45891 39050
46430 23573
4188 14342
18153 14387
34747 19911
19953 34775
45148 38432
11604 21983
9482 23336
20997 6427
49971 41247
42611 36238
8033 20499
44689 15188
36590 11751
31425 30009
26432 32484
37894 49675
19088 42962
44415 24214
7093 41119
46186 27610
8257 21412
20404 30486...

output:

result:

ok Queries used: 91671

Test #77:

score: 0

Accepted

time: 758ms

memory: 74256kb

input:

100000
772 6640
34573 35888
26102 46586
27214 31510
31641 42096
25367 36064
46612 5174
30359 45398
45529 5298
18703 15653
37225 14378
20198 2628
1682 10610
22536 48645
21151 47975
13411 44253
48368 47635
43727 27493
23392 17609
27565 42314
14079 42516
39063 40991
21872 42416
35625 25923
37160 49266
...

output:

result:

ok Queries used: 91640

Test #78:

score: 0

Accepted

time: 759ms

memory: 74180kb

input:

100000
44859 41358
31699 14015
5317 4599
38007 49099
48924 17056
11928 24361
24321 17000
27605 49737
16238 3641
30418 47220
41554 20496
34911 45700
41125 25040
44707 45333
29202 42315
17718 9863
36851 47243
24823 7858
43198 9145
6570 33503
3613 36005
12347 36488
37874 44699
43037 11895
45112 31954
4...

output:

result:

ok Queries used: 91624

Test #79:

score: 0

Accepted

time: 827ms

memory: 74192kb

input:

100000
47004 1247
1694 7949
8419 36221
4424 23055
8804 14262
20012 3749
44295 28261
15969 48623
9342 49931
23286 1285
37941 24941
33323 10845
13595 33111
46099 36865
25405 2346
4948 47757
25954 8472
6703 14663
4130 47761
12927 11042
29236 39552
1090 41551
35103 4464
19897 37694
19475 20250
7207 4145...

output:

result:

ok Queries used: 91682

Test #80:

score: 0

Accepted

time: 805ms

memory: 74180kb

input:

100000
3139 1979
46195 16609
33872 38664
6947 40484
12143 37205
16154 39988
41500 35191
10801 19213
15790 34551
25270 2783
30189 43777
6676 27507
2931 28492
47500 15785
33568 8790
30077 14146
11598 3929
21261 13566
49710 8531
37504 29736
21892 36428
3719 35866
2190 11266
22972 47917
37615 29806
2799...

output:

result:

ok Queries used: 91609

Test #81:

score: 0

Accepted

time: 768ms

memory: 74276kb

input:

100000
34775 33481
7266 30908
26834 46209
7664 32620
47210 48021
5497 16797
10724 47362
25794 3785
46827 29908
27544 46618
17502 35474
32986 18316
16379 34701
48756 33190
14320 28757
24168 6612
32814 13853
16376 28909
10264 35463
46458 3737
37352 26134
30876 30075
45588 45107
31227 7535
12270 31638
...

output:

result:

ok Queries used: 91698

Test #82:

score: 0

Accepted

time: 792ms

memory: 74012kb

input:

100000
40129 2870
28955 44038
26781 21256
18210 5087
46943 43715
49904 1023
20009 19911
27017 24886
45463 18472
24165 48674
8263 28731
25654 46339
11982 36117
16318 30991
20813 37786
27056 1719
22637 20580
26808 42545
40703 25923
3929 27697
27944 38052
32204 46645
26709 14319
33825 3779
44436 17908
...

output:

result:

ok Queries used: 91592

Test #83:

score: 0

Accepted

time: 944ms

memory: 74216kb

input:

100000
41092 26183
5104 1829
35282 13201
17344 46253
43347 35469
39824 47295
39400 21137
12970 36282
10810 30964
41738 32938
7539 20828
43630 49525
8349 13743
8824 27713
38105 45290
40728 41
8672 3319
10627 9071
30881 23974
33453 6281
25381 28192
16157 43173
17874 49453
35527 15568
17312 21428
14097...

output:

result:

ok Queries used: 91640

Test #84:

score: 0

Accepted

time: 821ms

memory: 74176kb

input:

100000
32608 24825
1865 13067
1429 41507
36287 12124
46486 9356
5915 9368
29337 21941
4777 8240
5193 46584
10394 49114
40362 16056
1996 3491
47516 46458
3491 37655
29064 30188
23592 31832
5964 10024
5080 31489
3035 36378
25174 44258
18655 22590
29025 10192
4794 6952
11680 16530
25640 47192
24398 370...

output:

result:

ok Queries used: 91639

Test #85:

score: 0

Accepted

time: 780ms

memory: 74272kb

input:

100000
33536 6939
10693 13132
8675 20939
24905 39491
42078 27013
48380 11862
31948 37371
5450 9560
14816 30056
32805 43360
16790 3692
25133 34252
36111 15525
5530 36927
14912 40532
2894 45014
11469 3306
11096 9859
29216 40921
18155 39660
15092 8111
40146 26892
28769 6837
48665 46612
27429 11217
2409...

output:

result:

ok Queries used: 91562

Test #86:

score: 0

Accepted

time: 774ms

memory: 73952kb

input:

100000
25783 44806
7423 34713
47417 4123
31560 985
30245 5241
45688 3849
22925 9366
16763 22673
4322 26704
12279 43691
44149 18005
23952 32080
15589 11411
5674 39126
15303 16096
30044 41455
23806 134
15301 3095
48285 14530
9397 6667
8994 13426
24637 23582
38141 31846
656 19754
15357 44927
19274 4469...

output:

result:

ok Queries used: 91440

Test #87:

score: 0

Accepted

time: 818ms

memory: 74224kb

input:

100000
5772 16538
34556 31084
2368 37240
12644 44081
1540 32761
17468 13252
35334 41668
7795 7636
14892 4724
9981 17998
16694 15069
39096 38023
37158 30606
48751 37015
8906 49580
14709 15222
42589 13095
5433 42765
10299 923
11549 28944
32177 26167
14261 20034
40816 14611
43434 9759
19382 34159
3459 ...

output:

result:

ok Queries used: 91740

Test #88:

score: 0

Accepted

time: 830ms

memory: 74224kb

input:

100000
34592 36335
46275 6857
30258 11772
2464 14615
8251 43892
13097 39952
14579 26389
6385 30184
42407 21191
17276 44535
14560 23418
41475 19818
37455 42713
11173 26181
12410 11593
13180 25542
4522 27701
36740 7125
7633 21274
34815 48887
8649 3271
7592 32504
45778 16080
44646 45304
23296 8469
3648...

output:

result:

ok Queries used: 91633

Test #89:

score: 0

Accepted

time: 866ms

memory: 74192kb

input:

100000
21285 22936
34056 7404
3525 24877
4999 45262
1840 23343
47432 31723
2148 39628
13889 39472
49389 4521
3598 28505
9372 1259
35679 4819
27124 37452
17998 4957
31964 40996
19088 21176
49803 34467
30610 36707
16215 7639
22704 43601
37022 24399
27713 49828
7842 114
26411 39399
45533 24933
41098 33...

output:

result:

ok Queries used: 91698

Test #90:

score: 0

Accepted

time: 728ms

memory: 74268kb

input:

100000
46659 2570
44376 11108
39478 41007
29431 40856
19170 39514
29349 27449
6394 23548
35037 43156
20437 31165
41909 36287
44193 41919
48193 33648
46526 18052
11492 7374
7972 41907
1390 4114
40015 2047
6291 1807
17121 14614
26717 49325
33940 48852
12943 37000
19604 17934
13142 21353
39829 39667
22...

output:

result:

ok Queries used: 91640

Test #91:

score: 0

Accepted

time: 710ms

memory: 74236kb

input:

100000
10205 5339
19331 37444
35898 39614
16509 33805
44416 9865
41517 35555
2779 15220
31979 39623
7116 14260
8647 3626
21151 34076
46731 14546
6796 44034
47885 437
7823 34061
25343 19908
36314 27456
32355 44331
18721 33009
35772 10076
6347 41014
31072 554
13900 27699
38218 9455
28511 19123
41543 1...

output:

result:

ok Queries used: 91654

Test #92:

score: 0

Accepted

time: 807ms

memory: 74184kb

input:

100000
35302 39308
43989 41843
38984 36308
9197 38178
18270 42538
36746 21640
49155 404
10351 16319
26326 12126
32515 31079
19672 10199
36256 31172
5402 3885
2039 36679
30976 25888
4681 11852
24884 16564
22301 22072
1205 25725
26746 35155
37054 10159
49303 32324
8919 20887
36792 18357
46115 37470
14...

output:

result:

ok Queries used: 91716

Test #93:

score: 0

Accepted

time: 830ms

memory: 74272kb

input:

100000
21400 31642
44516 3604
14761 39396
36805 1374
29312 48279
5771 19317
47869 27246
49451 6085
24611 16088
17484 1296
40461 22727
18031 3940
35077 42981
2381 14111
4206 42151
48257 33313
34950 25483
41688 32766
15204 34685
21337 10082
33925 29613
28230 13823
41981 5888
46384 14390
8567 3750
6306...

output:

result:

ok Queries used: 91626

Test #94:

score: 0

Accepted

time: 772ms

memory: 74184kb

input:

100000
32512 14555
20137 29973
28913 25704
10644 14308
1447 31398
30788 35226
13552 38443
30375 19475
19601 15553
14632 31058
2695 16209
22806 11566
38914 44918
1051 36103
5975 20111
48084 1108
12946 28487
34060 17110
6301 11370
42110 10906
33244 4188
14702 48457
5330 15988
39448 19927
48564 46717
1...

output:

result:

ok Queries used: 91688

Test #95:

score: 0

Accepted

time: 811ms

memory: 74188kb

input:

100000
41867 14515
39755 4420
301 22822
38909 35250
27486 7377
44074 12588
49638 12348
47826 15209
29859 3231
30029 29666
30934 22445
44774 47792
4878 25669
7935 35262
46834 35653
11979 34374
20281 2209
43341 11574
44973 5064
25894 36131
14019 32512
47893 7921
14452 25138
27341 44473
36036 11181
295...

output:

result:

ok Queries used: 91589

Test #96:

score: 0

Accepted

time: 771ms

memory: 74184kb

input:

100000
43371 17749
15706 41204
30124 9346
41254 10931
36731 42196
49341 16360
45402 18161
45488 1621
31838 21130
25640 28437
30762 19657
18386 23177
11547 41070
23137 48951
17552 779
27795 10146
3725 9887
16059 3303
27591 44614
11523 2824
13398 36397
45739 41822
37055 17095
29181 45828
15371 32598
2...

output:

result:

ok Queries used: 91757

Test #97:

score: 0

Accepted

time: 755ms

memory: 74292kb

input:

100000
29023 40169
49179 12916
43157 23379
9129 15839
12271 31123
37317 33930
37482 17017
32738 44952
39533 2541
33518 9019
1451 21362
1474 43428
4864 27190
36652 23071
7577 15651
40875 4582
36098 7588
49007 30839
27416 28772
22487 14716
1764 31344
5444 37009
41851 24308
14013 9908
39611 36957
3208 ...

output:

result:

ok Queries used: 91683

Test #98:

score: 0

Accepted

time: 789ms

memory: 74140kb

input:

100000
40052 24974
9569 19014
18078 14231
11379 24417
31815 1301
35334 22473
44104 43614
40071 9039
35197 25204
40500 17482
9092 10785
20032 31542
29554 4789
20977 6483
42882 47339
44197 17115
32802 43057
16081 8142
34132 16515
39238 25096
20173 25536
41710 25788
46131 30740
23536 39175
31789 16796
...

output:

result:

ok Queries used: 91734

Test #99:

score: 0

Accepted

time: 753ms

memory: 73948kb

input:

100000
30194 39325
45847 49349
3187 32967
10548 26188
19977 37397
25218 37529
5687 34653
44658 19141
15849 46345
8669 47900
48119 46744
41221 666
30131 18816
48400 41392
22945 23078
20086 28699
43234 5206
23107 2201
48330 28314
44479 37190
47203 17485
11757 45136
35305 28461
31034 15712
8067 45710
2...

output:

result:

ok Queries used: 91598

Test #100:

score: 0

Accepted

time: 808ms

memory: 74240kb

input:

100000
44054 14779
36090 21877
32211 11991
37713 41932
42057 40458
46613 40867
26559 44843
21168 48056
18472 37099
23938 12371
49346 32707
783 1617
39439 41729
48513 22634
43121 35840
16725 28613
18900 778
35892 20199
6813 1092
22096 3400
26399 42972
32949 19616
36175 39580
43620 15784
1671 13600
12...

output:

result:

ok Queries used: 91653