QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360777#4996. Icy ItinerarycrsfaaTL 245ms103328kbC++142.2kb2024-03-22 08:33:282024-03-22 08:33:28

Judging History

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

  • [2024-03-22 08:33:28]
  • 评测
  • 测评结果:TL
  • 用时:245ms
  • 内存:103328kb
  • [2024-03-22 08:33:28]
  • 提交

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=3e5+5;
vector<int> a[mxn];
unordered_set<int> b[mxn];
bool vis[mxn];
int ans[mxn];
int n,m;
void sf(list<int> &u)
{
	static int a[mxn];
	int cnt=0;
	for(auto x:u)
		a[++cnt]=x;
	random_shuffle(a+1,a+1+cnt);
	u.clear();
	for(;cnt;cnt--) u.push_back(a[cnt]);
}
void solve1()//有连边-无连边 
{
	memset(vis,0,n+1);
	vis[1]=1;
	int i,j,p=1,cnt=0;
	bool tp=0;
	list<int> u;
	for(i=2;i<=n;i++)
	{
		random_shuffle(a[p].begin(),a[p].end());
		bool fl=0;
		if(!tp)
		{
			for(auto x:a[p])
				if(!vis[x])
				{
					fl=1;
					p=x;
					break;
				}
			if(!fl)
			{
				tp=1;
				for(j=1;j<=n;j++)
					if(!vis[j])
						u.push_back(j);
				sf(u);
			}	
		}
		if(tp)
		{
			for(auto x=u.begin();x!=u.end();x++)
				if(!b[p].count(*x))
				{
					p=*x;
					fl=1;
					u.erase(x);
					break;
				}
			if(u.size()&&rand()%u.size()<=5) sf(u);
			swap(*u.begin(),u.back());
		}
		if(!fl) return;
		ans[i]=p,vis[p]=1;
	}
	for(i=1;i<=n;i++)
		printf("%d ",ans[i]);
	exit(0);
}
void solve2()//无连边-有连边 
{
	memset(vis,0,n+1);
	vis[1]=1;
	int i,j,p=1,cnt=0;
	bool tp=0;
	list<int> u;
	for(j=2;j<=n;j++)
		u.push_back(j);
	sf(u);
	for(i=2;i<=n;i++)
	{
		random_shuffle(a[p].begin(),a[p].end());
		bool fl=0;
		if(!tp)
		{
			for(auto x=u.begin();x!=u.end();x++)
				if(!b[p].count(*x))
				{
					p=*x;
					fl=1;
					u.erase(x);
					break;
				}
			if(!fl)
				tp=1;
		}
		if(tp)
		{
			for(auto x:a[p])
				if(!vis[x])
				{
					fl=1;
					p=x;
					break;
				}
			if(u.size()&&rand()%u.size()<=5) sf(u);
			swap(*u.begin(),u.back());
		}
		if(!fl) return;
		ans[i]=p,vis[p]=1;
	}
	for(i=1;i<=n;i++)
		printf("%d ",ans[i]);
	exit(0);
}
int main()
{
	ans[1]=1;
	n=read(),m=read();
	while(m--)
	{
		int x=read(),y=read();
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		for(auto x:a[i])
			b[i].insert(x);
	for(;;)
		solve1(),solve2();
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 28444kb

input:

4 4
1 2
1 3
1 4
3 4

output:

1 4 3 2 

result:

ok qwq

Test #2:

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

input:

5 0

output:

1 4 3 5 2 

result:

ok qwq

Test #3:

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

input:

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

output:

1 5 6 3 9 8 10 4 7 2 

result:

ok qwq

Test #4:

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

input:

2 1
1 2

output:

1 2 

result:

ok qwq

Test #5:

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

input:

2 0

output:

1 2 

result:

ok qwq

Test #6:

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

input:

3 1
1 3

output:

1 3 2 

result:

ok qwq

Test #7:

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

input:

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

output:

1 6 7 10 3 9 5 4 8 2 

result:

ok qwq

Test #8:

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

input:

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

output:

1 4 3 8 7 9 2 10 5 6 

result:

ok qwq

Test #9:

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

input:

15 40
12 11
11 6
5 11
15 14
10 14
15 5
1 11
10 12
4 3
6 4
4 9
2 11
6 12
13 7
7 9
10 9
1 2
9 11
2 6
7 14
2 9
3 13
9 1
2 7
8 11
1 10
13 1
4 15
3 7
2 15
6 5
10 15
4 14
15 6
2 4
3 11
1 14
2 8
1 8
10 7

output:

1 13 7 14 10 15 5 11 9 4 2 6 12 8 3 

result:

ok qwq

Test #10:

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

input:

15 1
13 6

output:

1 4 13 9 15 3 6 12 14 7 5 11 10 8 2 

result:

ok qwq

Test #11:

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

input:

150 150
110 99
80 122
55 67
24 47
73 68
150 13
94 140
146 59
136 28
94 134
131 2
26 105
65 79
57 37
116 102
84 16
110 78
72 5
34 8
8 43
83 57
49 146
43 112
54 139
95 13
11 95
75 29
29 30
52 14
118 56
4 51
18 146
31 113
56 69
44 14
63 123
44 66
101 122
52 10
16 118
71 93
22 113
28 88
5 108
16 48
84 1...

output:

1 141 30 29 75 109 76 97 94 133 108 89 113 8 60 81 49 129 57 35 105 38 25 62 126 22 10 147 16 78 143 68 31 39 59 99 130 111 86 100 3 118 18 128 56 117 135 20 9 96 51 101 50 134 11 47 67 131 28 19 61 53 80 88 15 52 119 72 4 104 13 83 91 145 144 125 14 103 54 136 79 140 92 63 45 40 71 107 24 37 17 150...

result:

ok qwq

Test #12:

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

input:

1500 1500
370 639
1046 375
1191 907
782 923
1369 196
998 194
640 331
309 631
1053 1076
887 1112
650 1437
2 1133
847 302
647 81
22 691
772 14
1112 62
266 1399
865 980
1302 1146
1007 575
1448 261
1489 1189
1134 1009
7 1175
1369 942
709 365
675 514
1021 1250
1415 2
976 746
564 388
431 326
43 147
385 81...

output:

1 1278 459 1314 785 356 771 1308 233 13 444 1044 1349 878 349 303 712 920 475 253 760 7 1427 697 888 347 515 88 1003 470 800 328 1279 1475 637 1359 806 1358 1408 1118 662 1491 529 898 931 454 846 932 482 247 574 5 142 793 109 35 684 491 62 1378 1048 880 1149 740 212 620 1131 953 85 502 392 1166 1342...

result:

ok qwq

Test #13:

score: 0
Accepted
time: 14ms
memory: 30628kb

input:

15000 15000
11602 9990
5492 14226
2633 14599
7956 12544
1258 1198
13788 3283
171 3770
8226 10782
915 6735
7186 14219
12806 1549
8783 5596
3692 9668
370 4654
13811 4032
835 12990
14273 14020
8902 7798
7405 4524
7476 1864
7786 14984
4367 13552
2927 2463
1929 3198
97 5800
14012 5674
6283 827
13860 1139...

output:

1 12454 5609 10027 7938 12035 12361 58 4017 5866 5966 12573 5963 2751 14916 14538 12905 13945 9724 11242 1029 3400 31 14595 11068 9438 7086 1686 14891 6135 4842 9024 11422 6674 3729 3505 11288 1685 10003 11908 10696 6775 4530 3600 858 5108 11540 6161 702 3992 6099 710 6740 13146 10119 7477 501 13604...

result:

ok qwq

Test #14:

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

input:

300000 0

output:

1 268729 44159 36852 234257 253807 240940 251657 135474 259275 192851 170309 263539 51373 16658 678 45073 95289 9108 39832 297544 70586 189026 278206 297323 204188 233677 246066 26033 146901 245898 226797 164729 35906 65458 40843 206666 110898 196754 119092 272482 79107 125547 235995 59216 240009 12...

result:

ok qwq

Test #15:

score: 0
Accepted
time: 86ms
memory: 39256kb

input:

300000 1
80856 110687

output:

1 268729 44159 36852 234257 253807 240940 251657 135474 259275 192851 170309 263539 51373 16658 678 45073 95289 9108 39832 297544 70586 189026 278206 297323 204188 233677 246066 26033 146901 245898 226797 164729 35906 65458 40843 206666 110898 196754 119092 272482 79107 125547 235995 59216 240009 12...

result:

ok qwq

Test #16:

score: 0
Accepted
time: 91ms
memory: 39304kb

input:

300000 100
254473 70041
278954 218026
54339 23948
90766 35432
145294 42945
10824 168971
162204 196321
137959 274421
274330 8901
113606 229638
136217 161945
232685 214848
91296 146678
8764 206628
297190 163150
140047 161791
188167 261504
261443 160497
262029 233857
112139 37654
43010 192683
3697 1727...

output:

1 268729 44159 36852 234257 253807 240940 251657 135474 259275 192851 170309 263539 51373 16658 678 45073 95289 9108 39832 297544 70586 189026 278206 297323 204188 233677 246066 26033 146901 245898 226797 164729 35906 65458 40843 206666 110898 196754 119092 272482 79107 125547 235995 59216 240009 12...

result:

ok qwq

Test #17:

score: 0
Accepted
time: 177ms
memory: 66008kb

input:

300000 100000
279619 105099
95580 46691
139476 105331
67098 144910
105689 84242
198438 147050
274697 179922
229381 179041
210820 243557
162433 137909
14644 17464
295783 151723
180167 63360
17314 119555
201506 121519
129982 11913
3312 283798
197026 175391
86210 36036
177182 150502
37900 95301
261630 ...

output:

1 268729 44159 36852 234257 253807 240940 251657 135474 259275 192851 170309 263539 51373 16658 678 45073 95289 9108 39832 297544 70586 189026 278206 297323 204188 233677 246066 26033 146901 245898 226797 164729 35906 65458 40843 206666 110898 196754 119092 272482 79107 125547 235995 59216 240009 12...

result:

ok qwq

Test #18:

score: 0
Accepted
time: 245ms
memory: 94676kb

input:

300000 300000
297121 280398
49505 181149
186167 88552
250816 195719
113345 180891
103968 274040
148345 167433
283785 32444
281156 62491
76167 222701
181130 69399
291957 220950
21996 17907
98113 270806
247895 36687
122761 248769
235623 41248
274601 174896
296046 235115
57460 64170
286130 15089
91951 ...

output:

1 195051 140606 174008 53918 12602 134053 7671 209510 81541 244561 213429 15530 185033 252970 9986 110335 284474 208878 56786 267013 70962 100802 96504 151478 252856 181623 267592 62205 251499 87038 111497 53442 286399 195188 128127 217472 234118 123527 242720 227709 131297 138155 155786 283737 6262...

result:

ok qwq

Test #19:

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

input:

1000 300000
794 378
253 365
792 287
235 482
50 807
795 174
786 980
763 645
615 440
364 542
209 856
925 709
965 709
755 592
242 870
960 978
253 404
164 439
931 998
443 318
663 958
560 445
970 245
192 631
321 621
120 472
402 520
939 454
436 893
840 577
112 961
509 9
815 190
357 128
52 433
554 967
384 ...

output:

1 449 181 763 630 76 947 666 392 857 403 997 845 600 471 425 520 700 459 366 822 806 668 875 710 780 967 132 319 876 705 141 688 118 546 799 923 278 640 502 477 209 129 178 432 294 290 664 38 564 398 858 583 275 762 122 287 205 701 530 123 906 607 33 339 862 190 537 801 304 354 904 895 839 681 109 4...

result:

ok qwq

Test #20:

score: 0
Accepted
time: 55ms
memory: 56784kb

input:

1500 300000
1189 1031
85 1047
1096 1290
1497 193
885 27
603 979
1438 1441
507 1256
1432 803
332 750
536 157
333 1248
1009 943
857 422
849 796
1399 814
911 481
836 36
1360 1175
592 737
277 672
551 331
849 1049
725 343
1312 112
889 544
1154 691
1387 1326
91 481
432 689
1051 248
1069 1499
499 194
748 1...

output:

1 745 343 151 1441 402 619 372 828 659 361 1405 601 621 368 1153 584 1020 964 940 458 1205 310 754 288 562 146 527 155 210 1211 1102 1075 899 767 27 123 507 1043 66 1424 179 1367 412 543 962 904 118 972 769 554 1076 184 841 502 1174 753 1078 460 401 843 1233 1083 206 996 192 608 296 1241 894 1348 11...

result:

ok qwq

Test #21:

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

input:

10000 300000
1236 4556
6003 6937
2217 6717
1150 1520
835 87
6994 6123
4263 8371
6772 4802
7302 3130
6157 4469
9918 3820
1997 5129
9662 7860
5882 9655
4931 8546
4776 1017
3925 6960
8114 6760
7793 3511
2958 3481
7244 3603
8609 4155
1832 2597
1639 6861
6563 8641
7870 3706
3772 4396
7696 6907
8722 1019
...

output:

1 8661 3400 3969 1972 9188 5609 452 2386 8410 7724 6897 2173 8720 2158 6887 6642 9348 9518 5343 7200 7510 3519 2092 3925 1357 9727 6857 9967 2804 1447 3447 2978 6194 3389 4189 7276 3146 9828 9354 9533 8031 1992 1178 8415 4802 433 8779 9113 4769 5516 3336 2063 9447 776 2564 4232 5339 729 1751 1945 57...

result:

ok qwq

Test #22:

score: 0
Accepted
time: 10ms
memory: 28376kb

input:

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

output:

1 3 4 6 2 7 10 9 5 8 

result:

ok qwq

Test #23:

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

input:

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

output:

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

result:

ok qwq

Test #24:

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

input:

1000 300000
1 965
2 965
3 965
4 965
5 965
6 965
7 965
8 965
9 965
10 965
11 965
12 965
13 965
14 965
15 965
16 965
17 965
18 965
19 965
20 965
21 965
22 965
23 965
24 965
25 965
26 965
27 965
28 965
29 965
30 965
31 965
32 965
33 965
34 965
35 965
36 965
37 965
38 965
39 965
40 965
41 965
42 965
43 ...

output:

1 365 814 265 992 712 534 248 353 521 605 777 687 964 735 597 146 309 345 91 379 476 903 208 824 306 975 83 174 112 499 445 108 505 729 351 694 148 847 871 931 92 209 923 375 737 381 707 709 228 704 333 225 123 869 677 627 175 748 216 158 832 105 193 999 554 610 477 562 459 458 792 726 601 134 473 2...

result:

ok qwq

Test #25:

score: 0
Accepted
time: 54ms
memory: 56116kb

input:

3000 300000
1 395
2 395
3 395
4 395
5 395
6 395
7 395
8 395
9 395
10 395
11 395
12 395
13 395
14 395
15 395
16 395
17 395
18 395
19 395
20 395
21 395
22 395
23 395
24 395
25 395
26 395
27 395
28 395
29 395
30 395
31 395
32 395
33 395
34 395
35 395
36 395
37 395
38 395
39 395
40 395
41 395
42 395
43 ...

output:

1 88 2991 2903 2099 798 633 2958 126 1450 591 1861 190 539 1599 277 2112 317 2022 556 1888 1301 269 1813 407 913 452 1085 1963 1571 2212 1977 1609 1171 2525 785 1319 1649 465 400 1710 1485 319 1911 2345 1069 1894 1581 2631 2514 1600 2602 566 255 192 2109 93 2464 2829 2736 1934 1827 620 2185 2732 144...

result:

ok qwq

Test #26:

score: 0
Accepted
time: 55ms
memory: 57608kb

input:

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

output:

1 4607 1006 2560 992 6566 2373 2145 4072 4573 6252 5337 2257 707 6522 5399 7841 9798 2707 5837 6647 4623 8875 6820 6202 2349 8144 9659 8690 5394 1882 1131 9433 4595 7885 1488 4434 7531 3956 2428 5947 9020 1755 3419 7480 6572 581 8835 1346 6149 7896 3859 5778 8934 9989 4505 2544 9532 9048 9652 7424 2...

result:

ok qwq

Test #27:

score: 0
Accepted
time: 73ms
memory: 57948kb

input:

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

output:

1 1513 22050 31561 12575 15643 16533 5018 37522 39633 12780 23833 4416 18782 16572 8681 12682 17615 9676 34248 31453 32515 8756 36492 31149 39437 38805 27564 34735 39202 4496 4924 11201 35580 17024 8073 1014 5434 33303 30966 34104 35482 37599 17693 22259 35843 22658 8019 23957 30780 3429 3992 25706 ...

result:

ok qwq

Test #28:

score: 0
Accepted
time: 88ms
memory: 69312kb

input:

100000 300000
1 97406
2 97406
3 97406
4 97406
5 97406
6 97406
7 97406
8 97406
9 97406
10 97406
11 97406
12 97406
13 97406
14 97406
15 97406
16 97406
17 97406
18 97406
19 97406
20 97406
21 97406
22 97406
23 97406
24 97406
25 97406
26 97406
27 97406
28 97406
29 97406
30 97406
31 97406
32 97406
33 9740...

output:

1 97406 39700 10856 97750 15583 83488 21441 85515 77943 94875 57112 5511 77902 29371 41047 58055 23982 92788 11281 88326 84884 68503 17105 27151 49818 93592 78574 3106 29706 94641 9937 83026 24522 63427 78031 86920 85380 94813 6690 36455 51402 62300 86806 61782 38220 93227 93822 34176 69488 69119 94...

result:

ok qwq

Test #29:

score: 0
Accepted
time: 179ms
memory: 103328kb

input:

300000 300000
1 193103
2 193103
3 193103
4 193103
5 193103
6 193103
7 193103
8 193103
9 193103
10 193103
11 193103
12 193103
13 193103
14 193103
15 193103
16 193103
17 193103
18 193103
19 193103
20 193103
21 193103
22 193103
23 193103
24 193103
25 193103
26 193103
27 193103
28 193103
29 193103
30 19...

output:

1 193103 197263 169371 295902 77955 225376 87759 111474 68144 78487 159201 45246 169533 244353 87069 230995 77614 144293 20520 37198 45265 70558 98002 248518 286704 226032 18395 227090 17665 28739 64155 120567 202760 290283 58047 123581 290495 227369 52099 110410 60092 270204 225346 245625 227689 23...

result:

ok qwq

Test #30:

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

input:

1000 249500
1 702
1 559
1 154
1 284
1 707
1 397
1 281
1 105
1 856
1 712
1 864
1 638
1 640
1 984
1 134
1 819
1 36
1 820
1 146
1 779
1 516
1 420
1 721
1 932
1 426
1 922
1 790
1 167
1 365
1 667
1 690
1 357
1 543
1 778
1 473
1 9
1 239
1 746
1 983
1 141
1 349
1 852
1 826
1 553
1 929
1 628
1 500
1 352
1 6...

output:

1 88 700 606 659 964 143 258 399 336 18 552 271 249 243 836 864 109 499 269 117 528 665 372 32 654 239 306 636 730 1000 33 111 587 628 232 66 264 646 402 134 43 237 738 505 256 352 736 430 328 489 238 305 392 98 406 463 218 391 377 862 930 35 724 813 404 311 592 826 742 721 366 662 734 220 153 574 4...

result:

ok qwq

Test #31:

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

input:

750 245875
1 596
1 476
1 375
1 129
1 650
1 604
1 579
1 302
1 574
1 322
1 351
1 206
1 107
1 535
1 597
1 135
1 516
1 330
1 515
1 151
1 357
1 146
1 4
1 150
1 85
1 15
1 655
1 227
1 549
1 311
1 560
1 705
1 273
1 249
1 307
1 191
1 398
1 691
1 621
1 257
1 268
1 729
1 593
1 61
1 139
1 630
1 172
1 740
1 306
...

output:

1 659 560 642 549 340 597 683 249 423 476 318 398 502 705 383 191 678 357 264 574 558 146 56 322 166 107 589 579 160 596 617 150 207 257 259 691 628 307 106 311 152 206 5 621 566 351 421 302 87 273 390 535 98 306 577 172 673 330 20 129 11 61 716 593 274 85 665 4 393 630 520 227 51 729 514 740 42 151...

result:

ok qwq

Test #32:

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

input:

750 245875
1 368
1 278
1 71
1 353
1 405
1 149
1 616
1 153
1 622
1 655
1 105
1 682
1 140
1 668
1 352
1 210
1 257
1 677
1 749
1 612
1 234
1 35
1 400
1 604
1 193
1 505
1 230
1 586
1 358
1 737
1 428
1 346
1 279
1 395
1 584
1 691
1 73
1 435
1 639
1 205
1 320
1 496
1 384
1 295
1 522
1 672
1 309
1 250
1 43...

output:

1 196 359 519 687 94 624 161 280 508 399 26 354 72 51 727 398 185 259 339 77 591 341 101 537 571 583 501 393 475 555 243 433 389 444 367 98 218 128 735 250 685 205 64 10 214 242 86 6 427 632 576 507 627 471 382 728 656 355 372 327 732 552 177 436 287 520 661 595 741 97 474 476 332 590 241 59 396 219...

result:

ok qwq

Test #33:

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

input:

750 101324
1 411
1 270
1 170
1 697
1 76
1 64
1 744
1 353
1 109
1 115
1 133
1 560
1 453
1 690
1 297
1 733
1 523
1 479
1 62
1 32
1 80
1 578
1 261
1 682
1 506
1 303
1 646
1 229
1 750
1 421
1 322
1 168
1 543
1 568
1 456
1 138
1 57
1 380
1 534
1 131
1 452
1 614
1 174
1 207
1 617
1 123
1 562
1 69
1 567
1 ...

output:

1 42 363 433 138 388 588 508 666 395 77 684 88 355 151 277 426 484 649 610 742 366 163 323 284 429 294 36 387 386 562 314 603 75 230 134 740 205 695 672 608 627 375 540 689 55 165 575 525 236 479 583 69 492 489 427 452 624 571 430 23 112 390 423 589 457 347 213 39 152 133 382 296 78 373 397 522 26 1...

result:

ok qwq

Test #34:

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

input:

750 45299
1 415
1 743
1 571
1 531
1 419
1 378
1 188
1 454
1 117
1 344
1 362
1 180
1 461
1 228
1 693
1 115
1 275
1 250
1 501
1 618
1 322
1 217
1 42
1 398
1 129
1 88
1 414
1 740
1 90
1 528
1 437
1 124
1 733
1 241
1 487
1 72
1 295
1 366
1 748
1 143
1 55
1 113
1 534
1 479
1 555
1 712
1 349
1 586
1 212
1...

output:

1 65 616 216 689 743 56 153 459 141 640 98 542 167 91 490 306 308 693 332 637 181 547 698 49 700 33 402 389 353 35 494 205 495 57 365 129 191 366 204 136 583 55 400 677 292 592 148 324 387 206 581 499 301 544 463 480 536 370 529 687 377 34 330 95 531 16 94 569 90 723 201 134 296 249 522 149 316 139 ...

result:

ok qwq

Test #35:

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

input:

750 258869
1 124
1 233
1 740
1 493
1 145
1 749
1 142
1 224
1 308
1 572
1 33
1 660
1 246
1 377
1 690
1 105
1 741
1 692
1 497
1 334
1 481
1 450
1 366
1 307
1 739
1 165
1 730
1 430
1 332
52 349
52 424
52 212
52 555
52 531
52 426
52 379
52 637
52 635
52 434
52 40
52 404
52 261
52 190
52 557
52 225
52 52...

output:

1 138 308 144 124 454 450 536 105 647 660 193 233 19 33 10 377 202 481 373 739 291 572 675 145 602 690 352 493 255 749 196 692 276 497 406 142 618 165 514 334 350 307 731 730 222 741 484 366 600 430 228 332 632 246 363 740 432 224 157 359 689 455 242 378 120 101 362 9 52 100 515 68 559 391 354 103 4...

result:

ok qwq

Test #36:

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

input:

750 1154
1 433
1 99
1 563
1 370
1 149
1 218
1 477
1 170
1 98
1 299
1 586
1 574
1 51
1 667
1 539
1 659
1 615
1 730
1 12
1 694
1 695
1 662
1 166
1 253
1 84
1 420
1 533
1 231
1 410
433 99
433 563
433 370
433 149
433 218
433 477
433 170
433 98
433 299
433 586
433 574
433 51
433 667
433 539
433 659
433 6...

output:

1 555 477 484 593 236 184 181 602 257 42 676 192 379 177 137 577 277 381 338 247 470 702 168 35 202 654 529 61 357 187 362 111 103 24 565 474 431 79 722 26 354 55 534 682 20 76 490 603 218 716 667 145 580 385 583 153 110 724 475 526 366 93 386 539 289 497 726 91 201 363 693 655 705 164 370 427 83 46...

result:

ok qwq

Test #37:

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

input:

750 1924
1 211
1 576
1 697
1 175
1 675
1 641
1 301
1 227
1 311
1 669
1 637
1 673
1 245
1 548
1 74
1 740
1 134
1 561
1 90
1 185
1 511
1 57
1 478
1 423
1 310
1 741
1 550
1 7
1 712
1 725
1 293
1 361
1 593
1 558
1 414
1 356
1 94
1 120
1 700
1 60
1 434
1 226
1 647
1 453
1 328
1 221
1 28
1 352
1 11
1 654
...

output:

1 592 65 585 16 75 52 748 281 185 183 15 340 17 476 680 237 85 488 238 546 316 502 530 130 228 584 178 286 552 153 704 358 4 253 633 172 60 93 443 272 628 114 716 176 726 600 291 41 598 610 208 683 315 212 557 53 214 169 374 331 309 367 441 587 136 221 454 156 737 391 406 525 99 64 487 131 146 517 4...

result:

ok qwq

Test #38:

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

input:

750 244699
1 235
1 228
1 716
1 27
1 55
1 706
1 313
1 247
1 131
1 120
1 446
1 25
1 615
1 351
1 712
1 606
1 406
1 324
1 356
1 182
1 622
1 230
1 497
1 511
1 163
1 137
1 630
1 434
1 273
1 350
1 297
1 674
1 605
1 109
1 707
1 101
1 78
1 691
1 133
1 705
1 354
1 115
1 735
1 384
1 211
1 364
1 386
1 663
1 54
...

output:

1 95 162 257 13 332 703 513 676 396 725 482 727 7 414 44 155 165 261 370 320 632 124 506 642 325 624 110 395 254 698 516 267 74 502 242 249 28 380 659 224 21 558 637 741 555 636 447 677 178 462 103 401 549 361 686 652 660 275 535 656 646 128 360 228 237 73 591 163 66 548 258 695 105 183 593 687 507 ...

result:

ok qwq

Test #39:

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

input:

1500 281624
1 1109
1 1191
1 775
1 218
1 867
1 1135
1 1484
1 72
1 523
1 502
1 1296
1 187
1 1241
1 1178
1 1099
1 305
1 962
1 431
1 813
1 368
1 755
1 722
1 404
1 1092
1 1263
1 999
1 704
1 1096
1 1234
1 645
1 504
1 246
1 365
1 624
1 838
1 1061
1 1458
1 430
1 738
1 1349
1 302
1 691
1 1098
1 1437
1 250
1 ...

output:

1 253 560 1230 676 166 822 1372 873 419 1457 680 709 1357 1105 587 578 957 464 133 716 545 665 473 1052 1496 432 809 1351 442 1331 1487 1363 56 1446 1358 596 344 1101 11 472 924 930 775 447 89 17 18 1324 234 854 1211 490 1395 1015 428 439 267 1310 169 222 847 1298 83 802 1048 1008 651 1418 361 414 2...

result:

ok qwq

Test #40:

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

input:

1500 281624
1 359
1 429
1 391
1 904
1 152
1 321
1 1361
1 435
1 1043
1 1059
1 669
1 1437
1 548
1 186
1 278
1 416
1 618
1 1472
1 634
1 806
1 503
1 713
1 1197
1 252
1 960
1 1341
1 366
1 302
1 623
1 226
1 52
1 1034
1 448
1 738
1 430
1 408
1 1366
1 874
1 727
1 18
1 240
1 1294
1 301
1 141
1 1046
1 369
1 9...

output:

1 838 679 1022 1367 1105 1384 1425 669 222 797 323 290 1329 406 300 1268 1031 470 461 1440 568 934 1185 559 200 1311 392 37 382 537 1109 994 684 1468 781 925 236 577 35 80 954 342 1111 254 923 879 1380 1223 830 750 1359 1228 547 104 1450 1491 1257 211 152 56 1168 347 326 571 120 1357 591 268 862 728...

result:

ok qwq

Test #41:

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

input:

1000 250000
1 576
1 827
1 255
1 901
1 254
1 217
1 553
1 531
1 436
1 209
1 339
1 765
1 21
1 610
1 235
1 613
1 495
1 918
1 299
1 512
1 628
1 68
1 4
1 421
1 422
1 858
1 587
1 458
1 154
1 487
1 205
1 687
1 227
1 279
1 394
1 608
1 802
1 656
1 548
1 286
1 752
1 544
1 821
1 328
1 751
1 175
1 801
1 871
1 99...

output:

1 674 787 411 657 509 142 525 58 714 746 618 313 371 232 656 869 437 91 719 488 55 281 89 46 535 321 29 218 468 612 986 245 503 803 57 897 258 238 768 794 500 412 290 229 561 434 593 489 546 767 638 625 962 786 337 103 646 730 32 312 750 666 361 521 782 826 629 532 31 106 136 268 177 83 404 522 299 ...

result:

ok qwq

Test #42:

score: 0
Accepted
time: 29ms
memory: 50700kb

input:

750 235576
1 584
1 479
1 457
1 589
1 456
1 195
1 284
1 120
1 220
1 340
1 566
1 134
1 661
1 666
1 742
1 702
1 563
1 246
1 370
1 415
1 388
1 159
1 532
1 209
1 121
1 157
1 573
1 272
1 77
1 454
1 487
1 471
1 545
1 600
1 256
1 262
1 612
1 58
1 131
1 607
1 403
1 124
1 691
1 571
1 534
1 740
1 43
1 482
1 19...

output:

1 109 274 142 394 410 519 499 97 616 490 716 375 209 381 263 488 238 717 474 75 197 740 21 657 37 559 20 524 580 372 325 107 452 231 17 571 589 697 547 137 720 604 183 426 71 114 327 578 198 126 261 683 30 166 94 371 128 636 341 251 736 443 681 34 414 606 141 235 572 661 399 725 733 593 415 293 33 2...

result:

ok qwq

Test #43:

score: -100
Time Limit Exceeded

input:

1000 250000
1 54
1 332
1 325
1 717
1 164
1 931
1 373
1 578
1 788
1 290
1 900
1 610
1 646
1 531
1 188
1 600
1 448
1 625
1 728
1 320
1 461
1 204
1 558
1 665
1 629
1 869
1 100
1 340
1 268
1 715
1 338
1 608
1 353
1 777
1 264
1 771
1 835
1 169
1 276
1 601
1 895
1 661
1 507
1 611
1 568
1 475
1 863
1 510
1...

output:


result: