QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#43859	#4578. Labyrinth	ZhaoZiLong	AC ✓	63ms	22712kb	C++17	891b	2022-08-11 13:35:44	2022-08-11 13:35:45

Due to the privacy settings of the submitter, you are not allowed to view this code.

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 5196kb

input:

output:

Possible
3
1 4 3 
3
1 2 3

result:

ok n=5, m=5: possible

Test #2:

score: 0

Accepted

time: 1ms

memory: 5060kb

input:

output:

Impossible

result:

ok n=5, m=5: impossible

Test #3:

score: 0

Accepted

time: 2ms

memory: 5284kb

input:

output:

Impossible

result:

ok n=3, m=3: impossible

Test #4:

score: 0

Accepted

time: 2ms

memory: 5244kb

input:

output:

Possible
2
1 5 
5
1 2 3 4 5

result:

ok n=5, m=5: possible

Test #5:

score: 0

Accepted

time: 1ms

memory: 5248kb

input:

2 2 1
1 2
2 1

output:

Impossible

result:

ok n=2, m=2: impossible

Test #6:

score: 0

Accepted

time: 2ms

memory: 5060kb

input:

2 0 2

output:

Impossible

result:

ok n=2, m=0: impossible

Test #7:

score: 0

Accepted

time: 2ms

memory: 5352kb

input:

2 1 2
2 1

output:

Impossible

result:

ok n=2, m=1: impossible

Test #8:

score: 0

Accepted

time: 1ms

memory: 5200kb

input:

2 2 2
1 2
2 1

output:

Impossible

result:

ok n=2, m=2: impossible

Test #9:

score: 0

Accepted

time: 2ms

memory: 5248kb

input:

3 0 3

output:

Impossible

result:

ok n=3, m=0: impossible

Test #10:

score: 0

Accepted

time: 0ms

memory: 5324kb

input:

3 1 3
3 2

output:

Impossible

result:

ok n=3, m=1: impossible

Test #11:

score: 0

Accepted

time: 2ms

memory: 5060kb

input:

3 2 1
1 2
3 1

output:

Impossible

result:

ok n=3, m=2: impossible

Test #12:

score: 0

Accepted

time: 2ms

memory: 5132kb

input:

output:

Impossible

result:

ok n=3, m=3: impossible

Test #13:

score: 0

Accepted

time: 2ms

memory: 5248kb

input:

output:

Possible
2
2 3 
3
2 1 3

result:

ok n=3, m=4: possible

Test #14:

score: 0

Accepted

time: 2ms

memory: 5220kb

input:

output:

Possible
3
1 2 3 
2
1 3

result:

ok n=3, m=5: possible

Test #15:

score: 0

Accepted

time: 1ms

memory: 5232kb

input:

4 0 2

output:

Impossible

result:

ok n=4, m=0: impossible

Test #16:

score: 0

Accepted

time: 2ms

memory: 5164kb

input:

4 1 2
3 2

output:

Impossible

result:

ok n=4, m=1: impossible

Test #17:

score: 0

Accepted

time: 2ms

memory: 5216kb

input:

4 2 2
3 2
1 4

output:

Impossible

result:

ok n=4, m=2: impossible

Test #18:

score: 0

Accepted

time: 1ms

memory: 5156kb

input:

output:

Impossible

result:

ok n=4, m=3: impossible

Test #19:

score: 0

Accepted

time: 2ms

memory: 5276kb

input:

output:

Impossible

result:

ok n=4, m=4: impossible

Test #20:

score: 0

Accepted

time: 2ms

memory: 5216kb

input:

output:

Impossible

result:

ok n=4, m=5: impossible

Test #21:

score: 0

Accepted

time: 2ms

memory: 5148kb

input:

output:

Possible
3
2 5 3 
3
2 4 3

result:

ok n=5, m=10: possible

Test #22:

score: 0

Accepted

time: 2ms

memory: 5196kb

input:

output:

Possible
4
2 1 4 3 
2
2 3

result:

ok n=5, m=11: possible

Test #23:

score: 0

Accepted

time: 0ms

memory: 3200kb

input:

output:

Possible
5
5 1 4 2 3 
2
5 3

result:

ok n=5, m=12: possible

Test #24:

score: 0

Accepted

time: 2ms

memory: 5152kb

input:

output:

Possible
3
4 2 5 
2
4 5

result:

ok n=5, m=13: possible

Test #25:

score: 0

Accepted

time: 2ms

memory: 5340kb

input:

output:

Possible
3
3 2 4 
2
3 4

result:

ok n=5, m=14: possible

Test #26:

score: 0

Accepted

time: 2ms

memory: 5192kb

input:

output:

Possible
3
1 5 3 
2
1 3

result:

ok n=5, m=15: possible

Test #27:

score: 0

Accepted

time: 2ms

memory: 5220kb

input:

output:

Impossible

result:

ok n=6, m=10: impossible

Test #28:

score: 0

Accepted

time: 2ms

memory: 3232kb

input:

output:

Impossible

result:

ok n=6, m=11: impossible

Test #29:

score: 0

Accepted

time: 0ms

memory: 5248kb

input:

output:

Possible
4
5 3 4 1 
2
5 1

result:

ok n=6, m=12: possible

Test #30:

score: 0

Accepted

time: 2ms

memory: 5316kb

input:

output:

Impossible

result:

ok n=6, m=13: impossible

Test #31:

score: 0

Accepted

time: 2ms

memory: 5252kb

input:

output:

Possible
4
3 2 6 4 
2
3 4

result:

ok n=6, m=14: possible

Test #32:

score: 0

Accepted

time: 0ms

memory: 5200kb

input:

output:

Possible
4
1 2 3 4 
2
1 4

result:

ok n=6, m=15: possible

Test #33:

score: 0

Accepted

time: 2ms

memory: 5248kb

input:

output:

Impossible

result:

ok n=7, m=10: impossible

Test #34:

score: 0

Accepted

time: 2ms

memory: 5200kb

input:

output:

Impossible

result:

ok n=7, m=11: impossible

Test #35:

score: 0

Accepted

time: 2ms

memory: 5348kb

input:

output:

Possible
5
3 1 4 2 6 
2
3 6

result:

ok n=7, m=12: possible

Test #36:

score: 0

Accepted

time: 1ms

memory: 5240kb

input:

output:

Possible
3
2 1 7 
5
2 3 6 5 7

result:

ok n=7, m=13: possible

Test #37:

score: 0

Accepted

time: 2ms

memory: 5056kb

input:

output:

Impossible

result:

ok n=7, m=14: impossible

Test #38:

score: 0

Accepted

time: 0ms

memory: 5152kb

input:

output:

Impossible

result:

ok n=7, m=15: impossible

Test #39:

score: 0

Accepted

time: 26ms

memory: 6176kb

input:

1000 200000 750
99 603
432 550
167 777
550 503
470 670
99 547
363 422
364 88
191 491
802 393
365 832
347 853
788 103
473 319
952 581
730 60
322 129
366 904
763 224
805 489
325 420
414 642
706 696
817 794
395 70
926 59
570 937
772 531
688 899
299 150
552 824
866 850
266 665
882 73
873 523
880 427
453...

output:

Possible
938
750 821 49 796 760 579 378 130 369 416 969 390 995 771 189 739 273 978 945 838 365 704 593 625 252 918 793 69 850 110 482 644 558 159 502 588 741 610 770 345 604 83 836 85 716 70 347 336 835 848 278 327 233 387 810 141 100 411 50 177 724 81 504 300 717 117 842 261 723 642 888 316 353 33...

result:

ok n=1000, m=200000: possible

Test #40:

score: 0

Accepted

time: 36ms

memory: 6604kb

input:

200000 200000 198052
4586 27672
17981 118299
94888 27703
63779 189872
197575 143914
102809 122055
161350 181460
115888 104037
103273 93758
73021 174644
70581 39955
59802 90498
140280 113445
176995 6850
4222 11494
52730 44233
176733 173360
27012 138898
14570 74558
78250 105659
123138 32176
156633 110...

output:

Impossible

result:

ok n=200000, m=200000: impossible

Test #41:

score: 0

Accepted

time: 28ms

memory: 6388kb

input:

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

output:

Impossible

result:

ok n=200000, m=199999: impossible

Test #42:

score: 0

Accepted

time: 38ms

memory: 7096kb

input:

200000 199999 1
113093 2
56617 3
177632 4
45501 5
179252 6
197091 7
86918 8
127628 9
110789 10
23064 11
15380 12
174677 13
25171 14
116220 15
7622 16
11370 17
17042 18
120335 19
103585 20
187829 21
92802 22
112939 23
79099 24
84969 25
108627 26
34045 27
139532 28
144356 29
123788 30
6664 31
96032 32...

output:

Impossible

result:

ok n=200000, m=199999: impossible

Test #43:

score: 0

Accepted

time: 58ms

memory: 22624kb

input:

200000 199999 1
28417 2
75238 3
35661 4
41668 5
163112 6
33492 7
146058 8
119064 9
89361 10
149891 11
176414 12
192281 13
85293 14
122872 15
73232 16
43049 17
135762 18
29240 19
165149 20
145318 21
74237 22
95382 23
85861 24
40685 25
88630 26
58014 27
54380 28
169636 29
117826 30
95492 31
6860 32
13...

output:

Impossible

result:

ok n=200000, m=199999: impossible

Test #44:

score: 0

Accepted

time: 20ms

memory: 6216kb

input:

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

output:

Possible
4
1 5 158258 159342 
3
1 2 159342

result:

ok n=200000, m=200000: possible

Test #45:

score: 0

Accepted

time: 18ms

memory: 6320kb

input:

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

output:

Possible
3
1 161406 8247 
2
1 8247

result:

ok n=199998, m=200000: possible

Test #46:

score: 0

Accepted

time: 31ms

memory: 7192kb

input:

200000 200000 1
1 2
1 4
1 7
1 25
1 41
1 463
1 939
1 3557
1 5506
1 49960
1 57865
2 3
2 11
2 56
2 159
2 472
2 12278
2 24433
2 52604
2 92202
2 143885
2 159205
3 6
3 28
3 53
3 2085
3 4390
4 5
4 8
4 9
4 71
4 238
4 380
4 596
4 1053
4 5713
4 7422
4 36656
4 106984
4 108732
5 10
5 29
5 31
5 91
5 141
5 173
5 ...

output:

Possible
18
1 4 5 10 14 51 152 240 274 921 1111 1739 3394 9147 48139 103379 125195 83488 
12
1 2 3 6 106 653 1898 2596 5211 8714 23920 83488

result:

ok n=200000, m=200000: possible

Test #47:

score: 0

Accepted

time: 35ms

memory: 7164kb

input:

199998 200000 1
1 2
1 8
1 51
1 109
1 236
1 264
1 368
1 2248
1 2726
1 4606
1 8197
1 9907
1 54812
2 3
2 4
2 5
2 107
2 5761
2 6840
2 10339
2 15124
2 16307
2 31159
2 92110
2 95473
3 7
3 14
3 21
3 27
3 28
3 33
3 37
3 353
3 2530
3 4176
3 5535
3 7378
3 20130
3 23521
3 27524
3 38779
3 62426
4 11
4 150
4 397...

output:

Impossible

result:

ok n=199998, m=200000: impossible

Test #48:

score: 0

Accepted

time: 34ms

memory: 15692kb

input:

200000 200000 1
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
5...

output:

Impossible

result:

ok n=200000, m=200000: impossible

Test #49:

score: 0

Accepted

time: 26ms

memory: 16148kb

input:

199998 200000 1
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
5...

output:

Impossible

result:

ok n=199998, m=200000: impossible

Test #50:

score: 0

Accepted

time: 24ms

memory: 6972kb

input:

199991 200000 1
1 2
1 3
1 4
1 5
1 23
1 45
1 79
1 141
1 174
1 291
1 826
1 1582
1 106574
1 146374
2 6
2 8
2 19
2 41
2 194
3 7
3 56
3 110
3 121
3 213
3 296
3 553
3 1087
3 5684
3 12620
3 36770
3 139163
3 151281
4 46
4 77
4 504
4 927
4 1531
4 2891
4 4093
4 22309
4 166814
5 11
5 12
5 13
5 22
5 100
5 299
5...

output:

Possible
7
1 4 46 125 246 1590 83394 
10
1 3 7 18 58 1456 1704 2362 52378 83394

result:

ok n=199991, m=200000: possible

Test #51:

score: 0

Accepted

time: 36ms

memory: 7164kb

input:

199901 200000 1
1 2
1 4
1 8
1 21
1 26
1 3862
1 4395
1 6044
1 9267
1 119347
1 167443
2 3
2 5
2 34
2 39
2 41
2 955
2 1242
2 9857
2 20264
2 30266
2 46919
2 53420
3 6
3 13
3 50
3 232
3 403
3 1120
3 2390
3 2983
3 10760
3 12799
3 43017
3 186442
4 7
4 42
4 158
4 223
4 671
4 2109
4 2814
4 4124
4 6207
4 8722...

output:

Possible
9
1 8 12 14 219 375 1402 3004 5349 
8
1 4 223 657 8978 48394 76894 5349

result:

ok n=199901, m=200000: possible

Test #52:

score: 0

Accepted

time: 27ms

memory: 7120kb

input:

199001 200000 1
1 2
1 3
1 12
1 28
1 48
1 100
1 104
1 114
1 124
1 292
1 372
1 3929
1 4064
1 16637
1 37706
1 56869
1 57879
1 89411
2 4
2 8
2 56
2 157
2 1262
2 1834
2 2434
2 11024
2 142777
2 171095
3 5
3 9
3 13
3 110
3 130
3 195
3 281
3 8440
3 105399
4 6
4 7
4 10
4 20
4 64
4 197
4 942
4 3751
4 9268
4 1...

output:

Possible
10
1 292 435 1285 2372 4442 5167 40696 62161 141733 
10
1 114 837 979 1025 3069 58579 65501 125325 141733

result:

ok n=199001, m=200000: possible

Test #53:

score: 0

Accepted

time: 38ms

memory: 6864kb

input:

190001 200000 1
1 2
1 5
1 49
1 59
1 203
1 452
1 551
1 958
1 1349
1 3069
1 3248
1 4082
1 31104
1 123082
2 3
2 6
2 39
2 55
2 149
2 154
2 324
2 488
2 1344
2 1405
2 7030
2 8119
2 44474
2 56110
3 4
3 7
3 8
3 30
3 137
3 277
3 892
3 1548
3 2709
3 5430
3 14156
3 15279
3 79538
4 14
4 15
4 29
4 123
4 205
4 14...

output:

Possible
9
1 452 509 528 42229 77986 109780 137671 44254 
6
1 59 343 512 888 44254

result:

ok n=190001, m=200000: possible

Test #54:

score: 0

Accepted

time: 33ms

memory: 7024kb

input:

199991 200000 1
1 2
1 3
1 6
1 10
1 12
1 14
1 15
1 30
1 595
1 1103
1 1172
1 1407
1 3246
1 12747
1 27902
1 48157
1 52331
1 53512
1 57264
1 68168
1 121994
1 138076
1 176407
2 4
2 11
2 19
2 20
2 31
2 35
2 43
2 79
2 80
2 292
2 1235
2 3453
2 4168
2 5012
2 125367
2 147212
3 5
3 7
3 8
3 40
3 56
3 108
3 139
...

output:

Possible
12
1 14 25 27 491 702 1177 3611 5932 67396 107019 90468 
10
1 10 32 44 105 535 5101 11871 42993 90468

result:

ok n=199991, m=200000: possible

Test #55:

score: 0

Accepted

time: 30ms

memory: 7120kb

input:

199901 200000 1
1 2
1 3
1 4
1 5
1 8
1 11
1 13
1 17
1 36
1 346
1 796
1 1204
1 4373
1 6334
1 6526
1 7551
1 12665
1 15696
1 53644
1 54043
1 64796
2 9
2 14
2 18
2 20
2 25
2 26
2 28
2 34
2 38
2 67
2 134
2 193
2 1068
2 1437
2 1709
2 2621
2 3671
2 4224
2 4657
2 6592
2 7899
2 10257
2 11797
2 16784
2 32076
2...

output:

Possible
9
1 17 66 522 5131 6927 12829 94188 175679 
8
1 13 29 413 2474 4475 10782 175679

result:

ok n=199901, m=200000: possible

Test #56:

score: 0

Accepted

time: 35ms

memory: 7084kb

input:

199001 200000 1
1 2
1 4
1 5
1 7
1 8
1 13
1 17
1 26
1 78
1 192
1 229
1 280
1 416
1 685
1 739
1 6891
1 9290
1 11026
1 21354
1 38853
1 61979
2 3
2 21
2 35
2 47
2 54
2 68
2 89
2 190
2 329
2 412
2 476
2 509
2 1345
2 3294
2 4196
2 4320
2 6117
2 16948
2 37252
2 46230
2 52789
2 55018
2 77562
2 80477
2 80535...

output:

Possible
5
1 229 391 10382 54410 
7
1 192 3687 7579 23365 167613 54410

result:

ok n=199001, m=200000: possible

Test #57:

score: 0

Accepted

time: 21ms

memory: 6936kb

input:

190001 200000 1
1 2
1 3
1 5
1 8
1 9
1 12
1 108
1 121
1 128
1 473
1 901
1 924
1 3191
1 5023
1 5047
1 5632
1 7381
1 10045
1 12625
1 16404
1 22731
1 24897
1 38463
1 50405
1 93426
1 143911
1 155466
2 4
2 6
2 7
2 11
2 16
2 86
2 112
2 209
2 323
2 390
2 1538
2 1562
2 1667
2 6741
2 16642
2 36177
3 10
3 17
3...

output:

Possible
8
1 5632 159970 21290 99714 113328 101188 127305 
7
1 128 641 1572 6134 57175 127305

result:

ok n=190001, m=200000: possible

Test #58:

score: 0

Accepted

time: 24ms

memory: 7080kb

input:

199991 200000 1
1 2
1 3
1 5
1 9
1 16
1 23
1 35
1 36
1 63
1 170
1 206
1 211
1 251
1 280
1 320
1 850
1 959
1 1013
1 1205
1 1336
1 1826
1 3090
1 4021
1 4295
1 10739
1 74716
1 87485
1 90537
1 110072
1 187277
2 4
2 6
2 7
2 8
2 15
2 33
2 37
2 38
2 41
2 77
2 80
2 89
2 94
2 146
2 238
2 1070
2 1370
2 2080
2 ...

output:

Possible
10
1 16 109 138 419 1082 3448 8354 32352 169673 
8
1 5 47 272 2168 18270 67242 169673

result:

ok n=199991, m=200000: possible

Test #59:

score: 0

Accepted

time: 31ms

memory: 6968kb

input:

199901 200000 1
1 2
1 3
1 7
1 12
1 23
1 25
1 29
1 45
1 128
1 239
1 330
1 450
1 670
1 734
1 1055
1 1068
1 1776
1 1962
1 5955
1 6983
1 7299
1 9086
1 10227
1 13412
1 14122
1 16330
1 23731
1 25582
1 27807
1 37585
1 157299
2 5
2 8
2 10
2 11
2 17
2 22
2 57
2 93
2 104
2 109
2 113
2 135
2 205
2 212
2 321
2 ...

output:

Possible
7
1 23 204 3713 25357 178264 60335 
4
1 12 171 60335

result:

ok n=199901, m=200000: possible

Test #60:

score: 0

Accepted

time: 38ms

memory: 7120kb

input:

199001 200000 1
1 2
1 3
1 4
1 5
1 40
1 61
1 210
1 225
1 321
1 328
1 420
1 510
1 883
1 902
1 1332
1 1474
1 1727
1 2286
1 2527
1 2810
1 2813
1 4597
1 7894
1 16116
1 25018
1 41731
1 45003
1 45365
1 59060
1 66542
1 70660
1 81690
1 91566
1 107169
1 124761
1 173619
1 184157
2 6
2 10
2 14
2 15
2 22
2 27
2 ...

output:

Possible
5
1 210 1607 6237 39846 
5
1 61 3186 18337 39846

result:

ok n=199001, m=200000: possible

Test #61:

score: 0

Accepted

time: 31ms

memory: 6860kb

input:

190001 199999 1
1 2
1 3
1 5
1 6
1 17
1 31
1 39
1 55
1 94
1 108
1 113
1 162
1 205
1 208
1 244
1 1003
1 1005
1 1122
1 1440
1 2835
1 2965
1 4056
1 8335
1 8670
1 12258
1 30616
1 47417
1 64628
1 94160
1 115208
1 127412
1 162298
1 179828
1 188179
2 4
2 7
2 9
2 15
2 18
2 52
2 84
2 86
2 241
2 258
2 308
2 33...

output:

Possible
3
1 8670 161033 
4
1 1003 50855 161033

result:

ok n=190001, m=199999: possible

Test #62:

score: 0

Accepted

time: 41ms

memory: 22712kb

input:

200000 200000 104982
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...

output:

Impossible

result:

ok n=200000, m=200000: impossible

Test #63:

score: 0

Accepted

time: 35ms

memory: 14820kb

input:

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

output:

Impossible

result:

ok n=200000, m=199999: impossible

Test #64:

score: 0

Accepted

time: 63ms

memory: 15408kb

input:

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

output:

Possible
100001
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169...

result:

ok n=200000, m=200000: possible

Test #65:

score: 0

Accepted

time: 56ms

memory: 14816kb

input:

199999 200000 1
1 3
3 5
5 7
7 9
9 11
11 13
13 15
15 17
17 19
19 21
21 23
23 25
25 27
27 29
29 31
31 33
33 35
35 37
37 39
39 41
41 43
43 45
45 47
47 49
49 51
51 53
53 55
55 57
57 59
59 61
61 63
63 65
65 67
67 69
69 71
71 73
73 75
75 77
77 79
79 81
81 83
83 85
85 87
87 89
89 91
91 93
93 95
95 97
97 99...

output:

Impossible

result:

ok n=199999, m=200000: impossible

Test #66:

score: 0

Accepted

time: 34ms

memory: 6700kb

input:

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

output:

Impossible

result:

ok n=200000, m=200000: impossible

Test #67:

score: 0

Accepted

time: 40ms

memory: 6696kb

input:

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

output:

Impossible

result:

ok n=200000, m=200000: impossible

Test #68:

score: 0

Accepted

time: 30ms

memory: 6972kb

input:

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

output:

Possible
18
1 3 7 14 29 59 118 237 475 951 1903 3806 7612 15224 30448 60896 121792 149567 
18
1 2 4 9 18 36 73 146 292 584 1168 2336 4673 9347 18695 37391 74783 149567

result:

ok n=200000, m=200000: possible

Test #69:

score: 0

Accepted

time: 2ms

memory: 5320kb

input:

706 911 614
457 348
47 544
598 243
533 483
512 79
243 181
200 604
219 541
255 431
588 467
590 242
282 99
519 620
156 227
49 20
662 280
46 391
436 666
91 648
254 438
103 90
548 400
256 613
308 552
60 629
609 280
599 214
542 520
168 700
291 682
497 675
371 692
212 300
175 158
164 172
146 285
594 518
6...

output:

Possible
6
614 255 144 308 381 123 
5
614 510 330 292 123

result:

ok n=706, m=911: possible

Test #70:

score: 0

Accepted

time: 3ms

memory: 5252kb

input:

928 1241 412
531 561
137 499
85 426
299 864
254 136
386 865
243 154
500 249
763 567
364 399
99 728
887 879
155 121
487 903
375 188
851 43
16 37
693 499
128 511
362 312
425 693
278 890
911 282
702 572
89 610
139 518
692 294
398 515
208 644
502 161
65 189
315 115
255 470
55 530
358 919
648 216
503 79
...

output:

Possible
16
412 701 631 12 1 689 481 698 834 560 846 740 726 677 763 567 
2
412 567

result:

ok n=928, m=1241: possible

Test #71:

score: 0

Accepted

time: 2ms

memory: 5136kb

input:

613 732 424
267 424
598 286
137 269
335 117
63 448
45 361
301 198
562 230
181 138
550 383
339 190
93 300
360 358
307 59
5 90
295 144
272 429
212 514
57 268
107 94
87 107
99 100
170 516
291 13
584 544
509 242
21 410
151 89
401 192
79 32
573 102
168 141
327 518
350 444
51 126
423 96
524 84
226 266
597...

output:

Possible
15
424 411 177 202 286 609 55 95 258 224 162 597 537 148 255 
4
424 436 292 255

result:

ok n=613, m=732: possible

Test #72:

score: 0

Accepted

time: 2ms

memory: 5224kb

input:

351 435 298
13 216
280 275
126 298
169 256
30 66
171 226
216 177
18 169
201 36
225 20
5 336
237 168
234 344
127 129
98 169
97 279
103 47
12 99
57 329
271 176
182 217
135 123
265 238
129 10
261 9
236 176
80 53
296 31
299 165
288 58
181 90
183 107
205 172
10 315
322 188
36 37
147 344
204 112
64 281
53...

output:

Possible
26
298 134 194 38 18 122 243 223 349 171 226 350 40 292 279 328 348 204 112 144 271 176 268 278 20 85 
3
298 62 85

result:

ok n=351, m=435: possible

Test #73:

score: 0

Accepted

time: 0ms

memory: 3168kb

input:

281 552 196
90 119
118 4
111 74
12 181
255 276
208 85
267 174
27 41
3 85
50 244
24 61
97 132
180 130
219 199
48 231
177 218
185 152
15 88
43 235
132 47
195 255
72 90
202 257
125 17
221 10
144 253
271 259
9 101
225 141
18 238
160 170
127 276
37 16
277 250
272 217
131 21
43 4
77 86
121 266
91 50
132 2...

output:

Possible
43
196 191 273 140 44 74 145 215 159 55 115 122 267 4 226 222 255 10 219 277 250 258 169 52 37 8 117 48 59 237 22 248 123 121 19 5 206 178 185 152 125 17 180 
2
196 180

result:

ok n=281, m=552: possible

Test #74:

score: 0

Accepted

time: 5ms

memory: 5396kb

input:

8429 14496 3632
4577 3524
817 8232
59 4774
7661 8131
7896 7689
7583 7248
5495 903
4803 5445
3965 5354
514 4829
3314 1506
777 2671
6553 7684
4051 5935
204 4178
3492 7413
4416 505
6986 1323
6657 3165
6741 3954
3504 8395
5730 472
6031 5626
170 7317
7930 3371
40 1806
4612 8264
6382 1811
2170 4434
6960 1...

output:

Possible
755
3632 3536 4488 2234 309 1215 5007 4331 681 4875 3064 2803 7941 4763 5354 387 411 4661 7994 5280 4920 3371 2036 1320 8141 2237 6318 6618 1277 2741 4584 2436 5812 8234 1412 4969 6039 218 6653 2156 5934 1161 2152 4971 6592 3128 7022 4226 2384 4512 976 8118 1201 4685 1397 4477 8129 7865 125...

result:

ok n=8429, m=14496: possible

Test #75:

score: 0

Accepted

time: 2ms

memory: 5360kb

input:

3840 3905 3313
925 919
1445 2066
3836 2817
2742 1678
2332 2257
2475 113
3682 913
1341 744
1788 2097
1064 2502
343 3463
2222 1024
423 3018
3347 2865
2402 1815
546 3351
2757 1005
166 3092
3662 2480
2546 3246
320 2601
2650 2319
2594 1540
440 1669
3648 3664
2536 3587
2856 771
2636 1439
815 3700
584 786
...

output:

Possible
28
3313 3696 2461 2111 1005 3512 203 3347 195 1233 711 104 1209 2551 504 303 3632 751 2851 756 1215 539 3261 2784 1645 177 1129 1121 
21
3313 2281 1776 3198 293 3338 1459 625 840 1356 3737 684 1552 2188 1874 3363 3060 3113 2972 757 1121

result:

ok n=3840, m=3905: possible