QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22754#2369. Joint ExcavationLFCode#AC ✓112ms32992kbC++141.8kb2022-03-10 16:03:212022-04-30 01:37:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:37:42]
  • 评测
  • 测评结果:AC
  • 用时:112ms
  • 内存:32992kb
  • [2022-03-10 16:03:21]
  • 提交

answer

//什么时候我才能有杜爷一半强啊/kk
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200086;
int n,m,tot,tp,st[N],sze[N],hs[N],h[N],a,b;
bool vis[N];
struct edge{int v,nxt;}e[N<<1];
vector<int>vec[N],mem[2];
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool add(int u,int v){e[++tot].v=v;e[tot].nxt=h[u];h[u]=tot;return true;}
int build(int np){
	sze[np]=1;vis[np]=true;
	for(int i=h[np];i;i=e[i].nxt){
		if(vis[e[i].v])continue;
		sze[np]+=build(e[i].v);vec[np].push_back(e[i].v);
		if(sze[e[i].v]>sze[hs[np]])hs[np]=e[i].v;
	}
	return sze[np];
}
bool Merge(int np,int S){
	mem[S].push_back(np);
	for(vector<int>::iterator it=vec[np].begin();it!=vec[np].end();it++)Merge(*it,S);
	return true;
}
bool dfs(int np){
	sort(vec[np].begin(),vec[np].end(),[](int a,int b){return sze[a]<sze[b];});
	st[++tp]=np;//printf("dfs %d %d\n",np,hs[np]);
	for(vector<int>::iterator it=vec[np].begin();it!=vec[np].end();it++){
		if((*it)==hs[np])continue;
		//printf("v %d %d\n",np,*it);
		if(a<b)a+=sze[*it],Merge(*it,0);
		else b+=sze[*it],Merge(*it,1);
	}
	//printf("np : %d , %d %d\n",np,a,b);
	if(a+sze[hs[np]]==b&&hs[np]){a+=sze[hs[np]];return Merge(hs[np],0);}
	if(b+sze[hs[np]]==a&&hs[np]){b+=sze[hs[np]];return Merge(hs[np],1);}
	return hs[np]?dfs(hs[np]):true;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int u=read();int v=read();
		add(u,v);add(v,u);
	}
	build(1);dfs(1);
	printf("%d %d\n",tp,a);
	for(int i=1;i<=tp;i++)printf("%d ",st[i]);puts("");
	for(vector<int>::iterator it=mem[0].begin();it!=mem[0].end();it++)printf("%d ",*it);puts("");
	for(vector<int>::iterator it=mem[1].begin();it!=mem[1].end();it++)printf("%d ",*it);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 0

output:

1 0
1 


result:

ok 

Test #2:

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

input:

20 25
17 14
5 14
3 18
14 2
13 4
18 8
18 20
2 20
2 1
2 19
2 10
4 10
4 15
20 1
20 19
20 10
10 1
10 19
1 19
1 6
19 9
6 11
6 12
9 16
9 7

output:

6 7
1 19 10 20 2 14 
9 7 16 18 8 3 5 
6 12 11 4 15 13 17 

result:

ok 

Test #3:

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

input:

20 22
19 6
11 6
2 6
6 15
15 13
13 12
12 7
7 15
15 12
7 13
3 14
8 14
20 14
14 13
12 5
5 18
5 9
5 4
7 16
16 17
16 10
16 1

output:

8 6
1 16 7 13 12 15 6 2 
17 5 4 9 18 19 
10 14 20 8 3 11 

result:

ok 

Test #4:

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

input:

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

output:

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

result:

ok 

Test #5:

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

input:

1000 3000
769 860
860 945
945 136
136 665
665 266
266 549
549 917
917 404
404 591
591 336
336 749
749 17
17 129
129 870
870 472
591 126
126 740
740 397
397 894
894 582
582 939
939 22
22 947
947 21
21 277
277 607
607 538
538 634
634 154
154 220
220 615
21 455
455 202
202 47
47 748
748 620
620 367
367...

output:

720 140
1 937 157 986 853 756 879 303 289 560 406 866 58 518 666 749 172 660 593 543 354 980 272 245 577 517 621 38 769 575 665 282 668 493 526 393 46 488 754 541 831 443 345 737 201 308 707 149 880 732 547 312 300 780 725 897 391 647 842 600 629 527 888 534 339 823 63 26 206 869 329 151 902 324 503...

result:

ok 

Test #6:

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

input:

1000 4000
464 484
484 988
988 735
735 247
247 269
269 16
16 46
46 40
40 543
543 236
236 107
107 660
660 58
58 270
270 705
705 161
161 797
797 444
444 395
395 710
710 488
488 162
162 202
202 353
353 430
430 804
804 371
371 47
47 819
819 566
566 92
270 275
275 860
860 208
208 704
704 580
580 317
317 6...

output:

798 101
1 64 168 93 179 843 117 17 894 601 148 657 819 416 207 400 302 449 560 565 9 870 94 505 45 638 765 831 271 164 216 669 933 855 804 28 663 647 426 278 469 957 112 793 319 977 725 631 399 791 996 269 965 12 77 773 105 628 983 245 191 696 883 707 694 317 170 836 468 944 895 471 731 888 755 917 ...

result:

ok 

Test #7:

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

input:

1000 6000
1000 60
60 97
97 994
994 431
431 393
393 698
698 447
447 254
254 450
450 669
669 480
480 436
436 354
354 243
243 33
33 182
182 632
632 212
212 445
445 303
303 404
404 199
199 427
427 746
746 259
259 724
724 892
892 170
170 655
655 634
634 342
342 914
914 387
387 336
336 2
2 255
255 91
91 6...

output:

874 63
1 317 496 117 183 669 438 813 767 587 168 553 757 442 294 543 188 886 950 7 28 665 966 807 789 395 356 353 854 298 36 970 597 717 683 600 727 868 389 401 151 472 555 368 189 705 86 544 592 612 280 262 504 691 413 759 396 283 323 870 392 156 794 619 719 926 707 865 714 739 340 126 888 758 530 ...

result:

ok 

Test #8:

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

input:

1000 8000
723 869
869 902
902 390
390 285
285 457
457 165
165 523
523 242
242 164
164 104
104 178
178 440
440 641
641 585
585 240
240 254
254 727
727 64
64 977
977 684
684 116
116 18
18 942
942 519
519 302
302 764
764 586
586 675
675 594
594 726
726 45
45 648
648 69
69 299
299 81
81 889
889 425
81 9...

output:

922 39
1 461 776 474 173 34 180 553 724 203 924 354 700 90 401 54 262 972 872 196 530 762 961 433 15 85 586 269 952 801 604 909 444 241 939 383 836 364 608 108 73 516 430 898 138 154 574 160 242 702 576 243 935 624 379 460 979 393 328 834 829 434 313 319 946 469 48 431 778 914 734 938 476 303 612 88...

result:

ok 

Test #9:

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

input:

1000 10000
218 188
188 791
791 374
374 366
366 572
572 625
625 522
522 568
568 329
329 92
92 12
12 288
288 944
944 624
624 918
918 711
711 945
945 478
478 846
846 139
139 136
136 967
967 873
873 528
528 674
674 62
62 767
767 866
866 116
116 505
505 354
354 48
48 898
898 712
712 611
611 192
192 35
35...

output:

932 34
1 175 460 690 869 74 785 258 156 893 172 373 924 682 338 310 920 101 140 806 257 45 307 579 741 304 322 476 932 522 405 498 144 506 242 337 348 967 700 736 105 349 161 562 71 730 415 724 122 29 882 649 218 219 954 644 468 669 138 126 996 765 536 195 466 837 205 596 353 698 216 568 640 173 201...

result:

ok 

Test #10:

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

input:

200000 200000
83736 8620
8620 193491
193491 152920
152920 20226
20226 21325
21325 140636
140636 32002
32002 80195
80195 108452
108452 168632
168632 106932
106932 60351
60351 122355
122355 17534
17534 128475
128475 94201
94201 152737
152737 110541
110541 36311
36311 139536
139536 140677
140677 106929...

output:

200000 0
1 143683 67657 119609 172952 46659 113438 170199 172671 109485 51898 40534 112542 67553 16487 16758 38949 163943 192221 145667 186372 125069 129931 88054 196332 196375 147672 55930 164686 102871 74244 143926 138154 3947 42300 184121 134377 96895 71143 97667 189274 140987 76576 106220 26066 ...

result:

ok 

Test #11:

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

input:

632 199396
610 33
262 576
194 573
384 105
380 233
413 271
58 364
323 515
91 617
556 263
248 611
354 399
518 455
550 560
518 472
575 474
196 618
377 279
301 620
497 27
579 302
223 24
524 334
342 388
371 74
436 450
357 167
427 531
574 292
260 472
140 419
586 295
79 149
328 368
107 535
366 205
281 90
1...

output:

632 0
1 176 134 229 561 467 593 260 219 112 128 507 246 58 580 206 249 423 145 537 285 560 509 502 238 540 587 59 82 7 428 582 524 619 607 622 320 185 372 317 391 506 141 60 239 235 347 569 375 172 610 585 113 434 446 624 471 531 264 35 103 255 620 461 558 433 296 165 46 66 180 331 481 47 163 594 55...

result:

ok 

Test #12:

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

input:

65535 131053
13817 11318
28659 34410
63271 15489
10084 63422
29749 57061
5867 26307
40175 32419
31340 13345
5136 33192
22203 64781
2465 53037
29628 13153
19198 26402
61161 54218
59819 20888
59221 24146
41674 37869
56244 62743
49261 1769
18689 39049
30380 46073
17387 35260
30443 47811
5353 53750
3246...

output:

4799 30368
1 28884 11697 42862 33193 55428 4519 45166 52718 22035 53143 53261 47988 7604 3009 62026 60836 45111 19295 33851 49986 59973 63172 53049 25198 59033 13051 5444 38523 38380 15746 14804 7150 38396 5726 60352 60114 15519 26752 10834 1452 30305 27793 7532 45165 50409 63944 13740 60585 27232 2...

result:

ok 

Test #13:

score: 0
Accepted
time: 112ms
memory: 23068kb

input:

190308 196044
157204 39611
62105 35612
111214 49950
85675 58461
90288 46652
128076 87202
21059 53523
72705 171266
106292 53461
42056 170541
158033 33735
26509 33264
133076 26361
121026 188201
72666 55549
47392 95463
105121 64880
186671 99295
144287 155507
126374 11188
116401 33541
182453 19740
13871...

output:

51964 69172
1 31563 15882 36409 148537 29225 40512 62661 47942 164720 165598 146896 8987 157650 110948 179310 137283 61737 125316 59818 144352 186700 73433 42206 29908 47534 29085 136399 137908 181426 45962 59313 147124 89936 101777 30210 129773 18274 93528 173429 2958 24748 34708 177685 36865 28267...

result:

ok 

Test #14:

score: 0
Accepted
time: 96ms
memory: 23468kb

input:

189204 194181
110380 112615
113412 71782
185972 117446
90208 77789
138638 181920
26086 126672
5551 16997
116879 28844
143629 101554
68409 6220
9904 15718
78941 96952
155642 80965
75426 177792
17590 129749
9414 107459
77182 80008
183488 97712
146496 511
92124 56877
63774 83306
100503 99589
81295 1408...

output:

55568 66818
1 82963 76297 161627 113001 62415 128109 74384 144159 68054 106128 13201 184886 40514 143267 90368 180315 59865 73804 28562 58670 116944 102514 84331 124627 92579 100276 121988 140137 67637 172494 123088 66672 45435 132684 105047 38366 83192 72566 124635 113239 103794 24285 132170 165375...

result:

ok 

Test #15:

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

input:

57648 199488
14726 1463
52862 17799
6336 30992
45880 6125
51562 25253
50289 19155
56581 28305
45085 41899
15056 55542
42722 55511
24319 3706
20643 47759
34125 17669
37474 49598
39972 9491
50424 8209
9453 15012
25327 51991
14267 12040
17388 52424
52756 2185
34092 18767
43182 24723
35763 23161
3170 28...

output:

42956 7346
1 18201 32870 1928 25223 16935 54295 14423 48670 12260 31518 18002 3118 47575 57414 50652 40147 26215 19310 9900 44028 30632 12657 47843 35056 17130 28552 16607 36101 21602 22784 13430 17106 610 44530 12814 38548 47778 29830 46849 46679 39163 21938 43392 31125 40990 5085 29141 25486 4812 ...

result:

ok 

Test #16:

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

input:

66715 199766
17587 30731
56632 16887
37051 5460
29252 58741
11869 56157
5040 51436
57858 47385
60636 9840
11275 42938
59593 21006
25647 44467
55570 9558
21851 12902
41386 34882
56453 9677
413 26389
26081 53713
22784 12564
42337 39787
57107 44572
52041 603
13696 29927
65508 46378
55 40192
56977 51133...

output:

49591 8562
1 58303 50419 51356 64277 32118 63576 454 49081 29849 41286 41358 16481 44820 19541 16346 32091 2892 33344 2883 20736 33366 26541 4232 34832 20212 22770 10005 65736 25806 39132 9498 20291 29591 3518 15486 59332 5180 30039 62084 21641 38043 8977 6020 44479 46407 6464 45561 11333 54100 2422...

result:

ok 

Test #17:

score: 0
Accepted
time: 99ms
memory: 24260kb

input:

190170 195465
2629 125899
162916 165958
140025 71443
152618 170663
174033 138921
67725 126246
120076 177041
91319 5047
117819 142413
37205 53432
171796 33846
61342 125907
88594 39102
182746 60081
142048 112062
15971 86835
114218 141326
173779 185185
51992 105887
120144 2227
153978 1114
171754 64620
...

output:

73772 58199
1 150373 79671 134527 42484 122779 181210 143937 72854 184330 119299 181921 38668 107764 101539 183310 58496 2062 158521 9850 41741 142164 37674 130165 412 130638 122460 87789 52190 72178 17809 136457 13247 78883 52442 24948 25263 40298 46708 119681 138698 71242 92652 163015 127860 16982...

result:

ok 

Test #18:

score: 0
Accepted
time: 104ms
memory: 24280kb

input:

189899 194541
170612 170993
144332 29034
17001 11340
69410 66705
74273 12178
28034 174156
111274 144547
24203 65035
158558 29767
163387 22891
87727 78790
94757 9058
17327 49332
127605 122013
38015 174772
35582 157839
152303 133417
171695 156575
2328 2463
53636 160820
119381 799
41843 40671
94397 354...

output:

74481 57709
1 147060 89797 176978 66938 189704 82029 146730 145517 159947 20376 18159 6343 37108 78741 86625 84262 77543 84835 115937 61541 82116 19626 35757 100445 44677 143646 175801 187490 129277 6655 58611 25620 85761 93032 45382 89213 120925 69351 112782 93984 130008 102670 123080 45165 14458 3...

result:

ok 

Test #19:

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

input:

61835 199331
18415 32775
61599 39208
11698 9837
29738 61808
55273 52808
19751 13058
40241 49183
533 24526
3687 30484
40337 35246
48445 57967
30675 16995
14197 42359
44535 28478
35124 42116
4345 48134
41451 53821
14105 25917
268 58877
51604 15465
42398 18952
7444 15980
41684 27200
45351 24537
37529 2...

output:

47369 7233
1 33920 10963 38585 11860 53679 16807 36690 60902 26110 11642 25169 21366 34168 13745 60115 26958 9009 48134 56001 36425 38642 44560 43310 58130 39591 6150 51927 30606 13669 2817 7062 42760 59460 36999 2055 21479 12371 51941 4266 57744 28262 57942 35275 40156 49399 2475 1079 23322 44631 1...

result:

ok 

Test #20:

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

input:

63337 199846
21418 52942
49451 23039
43718 45542
45918 41836
23920 47377
6180 21276
18798 25133
9930 31002
25244 54794
51681 12102
46163 34345
41833 33011
31769 26535
16578 47808
14938 6954
22712 52756
56846 25865
54863 10369
52324 49721
52481 23924
48066 50589
54956 58372
17311 45592
55921 50583
36...

output:

44145 9596
1 25156 21657 34176 46148 8738 51143 23499 23813 13963 31902 47397 40691 22883 44761 61857 63309 13070 45892 32733 3085 41408 12670 49142 32392 32581 2224 34345 17269 36651 53690 12405 29880 25806 39999 51613 55285 18714 796 32104 17282 56072 26105 25951 24940 51298 58739 21504 55501 2094...

result:

ok 

Test #21:

score: 0
Accepted
time: 95ms
memory: 18160kb

input:

200000 200000
10465 69937
69937 14729
14729 55961
55961 56619
56619 41166
41166 126257
126257 170152
170152 146252
146252 14017
14017 196651
196651 41107
41107 192888
192888 109152
109152 286
286 151318
151318 171322
171322 60562
60562 144557
144557 196342
196342 70875
70875 131680
131680 72498
7249...

output:

1292 99354
1 87954 93664 66046 105775 157522 21726 53944 18426 78960 51882 132348 22095 171498 182050 141013 94989 166455 112283 146594 83045 3732 16344 85660 123941 7968 1017 157125 187929 55896 37318 103653 122241 64643 91413 187528 52533 123623 166627 7854 31415 109827 163899 177255 179138 24643 ...

result:

ok 

Test #22:

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

input:

10000 200000
7470 4692
4692 7557
7557 5180
5180 2042
2042 3794
3794 374
374 7669
7669 9184
9184 6531
6531 2182
2182 3784
3784 5512
5512 8951
8951 9285
9285 9223
9223 2640
2640 6962
6962 3994
3994 4280
4280 6292
6292 4638
4638 2354
2354 4771
4771 5695
5695 690
690 517
517 8184
8184 751
751 4116
4116 ...

output:

9612 194
1 228 6246 9158 8760 7297 9846 534 1992 5997 5781 6919 4864 4562 4420 7476 5928 3648 3649 3607 7229 8400 7841 4806 5569 5835 2713 484 6644 6570 1337 9225 3683 3906 9490 5866 4512 2574 4884 6084 569 539 9604 2234 4497 2346 7485 4419 9521 9940 7406 3847 4655 3338 8599 1686 5353 1314 6647 6578...

result:

ok 

Test #23:

score: 0
Accepted
time: 80ms
memory: 17776kb

input:

192868 192867
149430 18345
18345 34346
34346 76193
76193 13133
13133 178290
178290 121695
121695 16199
16199 3138
3138 137097
137097 118812
118812 99316
99316 30191
30191 78550
78550 111582
111582 120756
120756 5960
5960 88801
88801 93958
93958 70959
70959 5776
5776 128695
128695 35159
35159 25369
2...

output:

948 95960
1 183794 50057 163986 54360 189073 85205 26001 123640 64420 41879 108726 23890 136239 100431 112912 168670 60910 8193 163839 106617 126031 15788 190059 117726 43171 182101 36257 85784 51481 158599 146014 123551 24861 2770 55711 117637 8755 77539 123753 80833 32135 8479 67462 81270 83485 16...

result:

ok 

Test #24:

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

input:

10000 200000
6480 5298
5298 7889
7889 4860
4860 7131
7131 7686
7686 5823
5823 6283
6283 7613
7613 7349
7349 3977
3977 7037
7037 6318
6318 3530
3530 5504
5504 8193
8193 7546
7546 7563
7563 3251
3251 8911
8911 5605
5605 3915
3915 635
635 6217
6217 8392
8392 4355
4355 8513
8513 675
675 9650
9650 267
26...

output:

9610 195
1 7163 77 3566 635 4111 240 8718 5629 9427 714 211 6606 6626 8936 6153 8949 5620 4617 8519 434 4627 1631 8612 3837 4724 5220 5722 2023 4790 8095 7534 3038 4417 9904 9448 953 8520 2590 8632 2393 4249 8933 8525 9177 5372 4416 9746 8031 6381 3401 3825 9766 2162 94 2278 6116 7747 2847 1074 4119...

result:

ok 

Test #25:

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

input:

5000 200000
3254 2589
2589 2644
2644 1877
1877 4910
4910 1176
1176 3423
3423 1392
1392 434
434 1488
1488 4175
4175 84
84 3476
3476 3348
3348 3377
3377 1950
1950 2340
2340 3213
3213 2182
2182 2684
2684 4165
4165 3741
3741 3699
3699 1050
1050 3121
3121 522
522 4705
4705 4885
4885 4227
4227 2677
2677 3...

output:

4922 39
1 4139 174 5000 2603 3393 3784 3397 87 3703 383 4036 4896 171 1920 4673 3029 3072 3399 1618 1407 2416 665 2167 311 1192 3832 3198 2606 62 3168 3312 3710 1908 4034 1435 2362 3732 2040 4937 4520 4596 3458 2709 1451 4962 3028 409 110 2984 4659 2237 1138 3253 4303 1120 3600 4535 2464 3618 4435 4...

result:

ok 

Test #26:

score: 0
Accepted
time: 39ms
memory: 32824kb

input:

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

output:

200000 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

result:

ok 

Test #27:

score: 0
Accepted
time: 37ms
memory: 32992kb

input:

200000 199999
200000 199999
199999 199998
199998 199997
199997 199996
199996 199995
199995 199994
199994 199993
199993 199992
199992 199991
199991 199990
199990 199989
199989 199988
199988 199987
199987 199986
199986 199985
199985 199984
199984 199983
199983 199982
199982 199981
199981 199980
199980...

output:

200000 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

result:

ok 

Test #28:

score: 0
Accepted
time: 69ms
memory: 32608kb

input:

200000 199999
152735 36834
36834 146215
146215 93059
93059 28002
28002 57147
57147 116744
116744 91899
91899 102349
102349 64373
64373 157271
157271 175204
175204 58636
58636 26665
26665 192069
192069 36653
36653 51824
51824 90366
90366 41647
41647 880
880 74117
74117 50073
50073 85090
85090 74269
7...

output:

187982 6009
1 152078 9158 184972 82074 62439 160418 116584 103428 62062 6525 27753 146431 165345 83044 85143 45662 89479 199121 49492 11728 88687 165319 163928 127727 121140 48147 143248 122738 5393 69519 142338 161332 175613 191660 176088 32574 61728 9450 74552 14720 114269 62279 135335 19967 33839...

result:

ok 

Test #29:

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

input:

10000 9999
5641 5640
2226 2225
5834 5833
4168 4167
2875 2874
3866 3867
2522 2521
5185 5184
1709 1708
842 843
3247 3248
9171 9170
418 417
34 35
9263 9262
534 535
8146 8145
2149 2150
1595 1594
3089 3088
4583 4584
2392 2391
6009 6010
7289 7288
5396 5395
4266 4267
6761 6760
4727 4728
4799 4798
5355 5356...

output:

72 4964
1 9732 9733 9734 9735 9736 9737 9738 9739 9740 9741 9742 9743 9744 9745 9746 9747 9748 9749 9750 9751 9752 9753 9754 9755 9756 9757 9758 9759 9760 9761 9762 9763 9764 9765 9766 9767 9768 9769 9770 9771 9772 9773 9774 9775 9776 9777 9778 9779 9780 9781 9782 9783 9784 9785 9786 9787 9788 9789 ...

result:

ok 

Test #30:

score: 0
Accepted
time: 56ms
memory: 20132kb

input:

200000 199999
112118 112117
34017 34016
101554 101553
5570 5569
69681 69682
66829 66830
21747 21748
102033 102034
64212 64211
64314 64315
31287 31286
86829 86830
125050 125051
23070 23069
168832 168833
90328 90327
177704 177703
153602 153601
168546 168547
70205 70204
1769 1768
60884 60883
63332 6333...

output:

316 99842
1 198767 198768 198769 198770 198771 198772 198773 198774 198775 198776 198777 198778 198779 198780 198781 198782 198783 198784 198785 198786 198787 198788 198789 198790 198791 198792 198793 198794 198795 198796 198797 198798 198799 198800 198801 198802 198803 198804 198805 198806 198807 1...

result:

ok 

Test #31:

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

input:

1000 4330
42 860
429 826
869 874
805 978
728 186
880 522
774 226
806 499
514 687
583 689
703 423
849 829
902 528
555 770
394 623
738 310
87 177
357 724
197 280
625 417
2 512
556 530
168 520
219 791
519 833
557 750
957 904
551 533
225 115
424 657
89 715
920 175
281 488
533 392
769 656
972 202
40 433
...

output:

36 482
1 121 366 498 21 489 755 530 675 118 714 643 132 845 181 340 768 140 130 153 891 636 617 650 733 881 737 565 676 246 936 216 687 186 50 728 
785 811 756 546 385 248 741 66 47 413 300 358 753 353 670 819 193 508 450 978 344 805 715 612 89 227 933 927 705 823 359 935 481 289 157 134 438 439 776...

result:

ok 

Test #32:

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

input:

1001 5000
981 46
705 536
493 918
424 112
529 920
765 775
688 158
115 64
975 751
426 387
89 880
845 167
742 977
803 670
199 682
335 135
264 786
1 309
579 582
609 19
843 1000
212 971
317 826
372 364
917 452
588 120
892 996
477 752
499 348
263 471
933 561
690 434
158 682
458 692
718 204
365 17
432 929
...

output:

83 459
1 150 473 130 859 290 711 605 59 465 221 4 517 738 736 756 309 902 101 980 822 889 163 825 911 60 146 35 394 316 492 138 256 661 958 803 740 564 397 23 390 282 815 318 183 259 950 416 406 584 129 739 925 446 923 453 208 58 376 467 629 228 881 577 990 322 135 606 127 632 241 153 237 733 480 30...

result:

ok 

Test #33:

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

input:

1500 6000
229 979
206 199
1177 389
693 283
1430 1362
822 529
602 654
1195 1308
567 593
1400 366
1400 1330
1231 1170
828 747
393 144
949 765
1263 633
1123 1022
824 1190
162 644
1172 620
613 800
760 334
49 277
924 567
20 742
1201 914
1362 1388
785 940
1252 661
910 985
1293 1198
653 514
1199 1310
1396 ...

output:

116 692
1 916 31 761 471 396 1168 166 1479 548 948 658 773 42 873 1325 47 90 1169 148 1028 450 731 359 881 1475 159 1320 746 1382 578 1078 378 1285 432 406 1369 1485 629 174 1349 356 1084 718 1381 352 1268 1404 368 528 53 1280 825 1293 878 116 842 543 123 114 1467 584 210 942 977 320 1414 1066 659 1...

result:

ok 

Test #34:

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

input:

10003 95661
8092 6584
545 4577
4169 7949
7557 830
2156 2824
8860 6413
9673 4215
1503 9603
2093 7875
5906 4574
9893 2002
2242 1976
7649 6808
8583 9250
4236 4733
8767 2428
4573 9070
7278 1441
656 1325
9908 690
6645 4472
4135 5803
3631 4120
2512 1368
5353 7445
2533 954
8162 5870
5988 9570
8280 3274
215...

output:

139 4932
1 9903 4312 3675 4912 2091 8981 1586 3555 1620 7527 5748 1024 4363 5847 421 6380 5614 93 3997 9417 283 6573 4849 6756 3433 3851 5366 2907 9206 2959 2397 8316 3084 3225 4234 9621 7043 2829 5722 745 5732 4001 4385 9538 2810 7380 9595 4829 6300 2517 774 4347 7634 2652 3966 7270 624 7818 6564 2...

result:

ok 

Test #35:

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

input:

10000 63482
9956 6120
8634 1549
933 8173
5984 8157
1540 6235
6771 4790
9190 1205
2900 8761
6223 7171
7131 6777
9220 8923
7229 9749
723 8485
3449 6521
9201 2455
1680 8590
6124 4632
8690 4603
7840 9199
3290 663
6613 9240
4743 2753
1301 755
9143 9056
4533 754
2930 8516
4333 9255
4558 5841
9612 6436
981...

output:

98 4951
1 8017 3724 6168 8644 5825 7455 2972 1047 1188 1858 4809 9475 7595 1055 345 5221 5145 7888 1407 1288 6790 8294 8948 1548 9 1810 3834 6822 4852 6051 9703 3549 1185 170 3636 2078 1508 5394 1479 2741 8669 357 8834 3066 5121 115 2608 3070 3014 874 7750 620 8143 5541 3320 363 185 1416 9128 266 60...

result:

ok 

Test #36:

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

input:

10001 200000
7990 8651
9078 312
4894 1058
4121 2912
5524 6771
866 9344
7969 5279
5441 6964
2348 1113
5446 3185
9933 9702
4809 3753
3664 8028
9983 7200
9224 373
42 9423
873 3835
8057 8877
6644 2959
3592 3271
306 8157
7804 2381
1102 424
1923 8652
5067 9232
6679 9850
1190 2261
787 4914
1609 5097
3589 4...

output:

473 4764
1 609 3613 923 61 5255 5117 252 9669 1415 6531 8969 7038 2326 8966 9067 935 3458 4704 4130 7014 4111 3340 5724 1138 537 9176 1594 6290 9562 7200 6751 3294 7419 7410 330 3991 3729 4136 7944 4754 1039 736 7359 1268 1487 6204 8817 2230 8250 5958 6592 159 8431 3923 3031 5178 5862 6484 9983 767 ...

result:

ok