QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#590123	#31. Railway	Nova_NightWind0311	100 ✓	50ms	20240kb	C++20	2.2kb	2024-09-25 21:45:24	2024-09-25 21:45:27

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

Subtask #1:

score: 8

Accepted

Test #1:

score: 8

Accepted

time: 1ms

memory: 9996kb

input:

output:

6
1 4 6 7 8 9

result:

ok 2 lines

Test #2:

score: 8

Accepted

time: 4ms

memory: 8616kb

input:

10000 200 20
1 2
1 3
1 4
1 6
1 228
1 1392
1 1486
1 5068
1 6341
1 6847
2 8
2 10
2 23
2 25
2 34
2 56
2 103
2 341
2 1574
2 5024
2 9238
3 5
3 59
3 89
3 572
3 1539
4 12
4 183
4 2192
4 3944
4 8883
5 7
5 16
5 18
5 40
5 73
5 126
5 414
6 9
6 14
6 15
6 17
6 88
6 2577
7 45
7 63
7 68
7 292
7 484
7 1249
7 1522
7...

output:

76
1 2 4 11 12 14 15 22 32 33 34 39 45 56 62 63 74 81 103 117 122 132 139 156 161 213 228 234 263 267 273 291 307 323 375 472 567 663 688 733 936 1036 1125 1378 1635 1903 2124 2193 2363 3317 3318 3496 3539 3540 4231 4232 5044 5049 5524 5564 5749 5885 5886 6118 6157 6158 6775 7241 7242 7835 8416 8417...

result:

ok 2 lines

Test #3:

score: 8

Accepted

time: 4ms

memory: 10708kb

input:

10000 200 55
1 2
1 4
1 14
1 58
1 366
2 3
2 7
2 40
2 166
2 201
2 399
2 1327
2 5058
3 6
3 11
3 16
3 25
3 34
3 104
3 156
3 1735
4 5
4 10
4 27
4 68
4 72
4 80
4 506
4 954
4 1802
4 3857
4 8289
5 35
5 555
5 1231
5 2177
5 4045
5 9735
6 9
6 13
6 18
6 21
6 114
6 121
6 139
6 203
6 345
6 411
6 1579
6 1915
6 697...

output:

23
1 2 6 7 8 14 15 18 23 40 53 67 83 92 99 108 224 254 668 691 777 782 1153

result:

ok 2 lines

Test #4:

score: 8

Accepted

time: 1ms

memory: 7936kb

input:

output:

12
6 7 8 9 10 11 12 13 14 16 17 18

result:

ok 2 lines

Test #5:

score: 8

Accepted

time: 1ms

memory: 8004kb

input:

20 10 5
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
4 6 7 10 11
4 5 7 10 12
4 5 6 10 13
4 4 6 10 12
4 4 7 11 13
4 6 7 8 9
4 6 7 8 9
4 7 8 9 10
4 7 8 9 10
4 6 7 8 10

output:

5
6 7 8 9 10

result:

ok 2 lines

Test #6:

score: 8

Accepted

time: 3ms

memory: 8960kb

input:

10000 450 12
1 2
2 3
3 4
3 6160
3 6779
4 5
4 7984
4 8385
5 6
5 7179
5 9305
5 9772
6 7
6 9263
7 8
7 6479
7 7146
8 9
8 5543
9 10
9 5632
10 11
10 5039
11 12
11 5799
12 13
12 8937
13 14
14 15
15 16
15 7082
15 7698
16 17
17 18
18 19
19 20
19 7916
20 21
20 5964
21 22
21 9318
22 23
23 24
24 25
25 26
25 608...

output:

4907
43 44 45 47 50 51 53 54 55 56 57 58 59 61 62 63 65 67 68 71 72 73 75 77 79 80 82 83 86 89 92 94 97 100 103 104 106 107 108 109 110 112 114 115 116 118 119 121 122 124 126 129 130 131 132 133 134 137 138 139 140 141 143 145 148 149 150 151 153 155 157 158 159 162 164 167 169 171 172 173 174 176 ...

result:

ok 2 lines

Test #7:

score: 8

Accepted

time: 3ms

memory: 8724kb

input:

10000 101 2
1 2
1 5405
1 5864
1 6579
2 3
2 2401
2 3038
2 3315
2 4065
3 4
3 2614
3 3461
3 7341
3 9605
4 5
4 1688
4 2993
5 6
5 2222
5 4151
6 7
6 4734
7 8
7 9460
8 9
8 4046
9 10
9 1576
10 11
10 1056
10 5071
10 5219
10 6147
11 12
11 5479
11 9599
12 13
12 1155
12 4510
13 14
13 1577
13 8132
13 8434
14 15
...

output:

515
77 81 83 84 86 88 91 92 118 120 122 127 140 145 149 154 184 187 190 192 193 245 251 252 257 294 378 381 385 386 388 389 391 410 464 465 481 483 487 508 509 511 512 520 521 522 523 524 525 622 626 627 630 650 651 653 711 712 713 716 717 719 720 725 759 760 807 808 812 833 834 835 838 840 844 848 ...

result:

ok 2 lines

Test #8:

score: 8

Accepted

time: 3ms

memory: 8664kb

input:

10000 1000 2
1 2
1 4
1 14
1 28
1 56
1 64
1 65
1 70
1 94
1 99
1 100
1 106
1 110
1 130
1 132
1 135
1 137
1 141
1 178
1 183
1 186
1 196
1 202
1 205
1 223
1 228
1 244
1 251
1 265
1 269
1 272
1 276
1 284
1 286
1 294
1 307
1 308
1 330
1 353
1 358
1 363
1 364
1 377
1 379
1 388
1 396
1 427
1 483
1 487
1 492...

output:

197
1 2 82 205 211 245 306 340 371 693 735 789 839 853 994 1008 1010 1409 1411 1421 1610 1632 1693 1764 1768 1771 1828 1846 1862 1874 1883 1885 1893 1905 1927 1968 1989 2025 2026 2027 2066 2069 2087 2106 2177 2189 2193 2336 2344 2360 2394 2522 2616 2733 2844 2913 2992 2998 3002 3039 3058 3060 3173 3...

result:

ok 2 lines

Test #9:

score: 8

Accepted

time: 0ms

memory: 10744kb

input:

10000 1000 1000
1 2
1 4
1 6
1 8
1 14
1 44
1 216
1 529
1 671
1 695
1 998
1 1108
1 1339
1 1426
1 1474
1 1597
1 1737
1 1762
1 2105
1 2401
1 2428
1 2586
1 2720
1 3310
1 3910
1 4018
1 4400
1 4499
1 4725
1 4896
1 5163
1 5197
1 5308
1 5382
1 5455
1 5496
1 5505
1 5737
1 5805
1 5967
1 6044
1 6278
1 6475
1 65...

output:

result:

ok single line: '0'

Test #10:

score: 8

Accepted

time: 1ms

memory: 7964kb

input:

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

output:

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

result:

ok 2 lines

Test #11:

score: 8

Accepted

time: 1ms

memory: 7972kb

input:

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

output:

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

result:

ok 2 lines

Test #12:

score: 8

Accepted

time: 0ms

memory: 10056kb

input:

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

output:

10
2 3 5 6 8 9 13 14 18 19

result:

ok 2 lines

Test #13:

score: 8

Accepted

time: 0ms

memory: 8004kb

input:

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

output:

13
4 6 9 10 11 12 13 14 15 16 17 18 19

result:

ok 2 lines

Test #14:

score: 8

Accepted

time: 0ms

memory: 7928kb

input:

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

output:

9
4 7 8 9 11 12 13 15 17

result:

ok 2 lines

Subtask #2:

score: 15

Accepted

Test #15:

score: 15

Accepted

time: 12ms

memory: 8704kb

input:

10000 1500 25
1 2
1 5
1 10
1 14
1 76
1 1625
1 1969
1 2025
2 3
2 34
2 320
2 519
2 577
2 2340
2 3157
2 7075
2 8630
3 4
3 38
3 215
3 248
3 272
3 1597
3 1752
3 1853
3 2104
3 5171
3 8467
4 7
4 9
4 12
4 30
4 436
4 1404
4 3559
5 6
5 8
5 60
5 74
5 79
5 281
5 627
5 770
5 848
5 2371
5 6713
5 9756
6 13
6 73
6 ...

output:

1430
1 2 3 4 5 9 10 12 13 18 19 20 21 29 30 31 32 33 36 37 38 39 40 42 48 49 50 51 56 57 58 59 60 61 65 66 67 68 71 72 73 74 75 76 80 81 82 83 85 86 89 91 92 93 94 95 97 98 99 101 102 103 105 106 107 109 110 111 112 117 118 119 120 122 123 131 132 135 137 138 139 140 142 145 150 151 152 153 156 159 ...

result:

ok 2 lines

Test #16:

score: 15

Accepted

time: 12ms

memory: 8664kb

input:

10000 1500 11
1 2
1 3
1 8
1 27
1 28
2 4
2 7
2 20
2 64
2 91
2 302
2 602
2 931
3 5
3 45
3 52
3 95
3 107
3 375
3 650
3 826
3 1315
3 3089
3 8256
4 29
4 44
4 161
4 219
4 877
5 6
5 11
5 24
5 40
5 62
5 80
5 158
5 292
5 506
5 625
5 674
5 1489
5 1601
5 3095
5 3249
5 3332
5 3550
5 4551
5 9959
6 12
6 13
6 14
6...

output:

3965
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 42 43 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 73 74 75 77 78 79 80 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 98 99 100 101 102 107 108 109 110 111 112 113 115 11...

result:

ok 2 lines

Test #17:

score: 15

Accepted

time: 17ms

memory: 10672kb

input:

10000 1500 5
1 2
1 3
1 5
1 10
1 18
1 29
1 82
1 114
1 213
1 339
1 1723
1 2506
1 3390
2 4
2 27
2 33
2 286
2 3922
2 7907
2 9579
3 6
3 7
3 13
3 38
3 131
3 229
3 582
3 1132
3 1575
3 2046
3 7395
3 7534
4 24
4 63
4 165
4 740
5 8
5 26
5 30
5 170
5 365
6 209
6 394
6 663
6 676
6 769
6 4426
7 9
7 12
7 32
7 79
...

output:

6846
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29 30 31 33 34 35 36 37 38 39 40 41 43 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 89 90 91 92 93 94 95 96 98 99 100 101 102 103 104 105 1...

result:

ok 2 lines

Test #18:

score: 15

Accepted

time: 4ms

memory: 10964kb

input:

10000 1991 399
1 2
2 3
2 6311
3 4
4 5
5 6
6 7
6 8587
6 9209
7 8
8 9
8 6791
9 10
10 11
11 12
11 5348
12 13
12 9153
13 14
13 5582
13 6394
13 6528
14 15
15 16
16 17
16 8829
17 18
17 7764
18 19
18 5926
19 20
20 21
20 8222
21 22
21 5800
21 9267
22 23
23 24
24 25
25 26
25 8998
26 27
27 28
27 9850
28 29
29...

output:

3584
875 876 877 878 879 880 884 885 886 887 888 889 890 892 893 894 895 896 897 899 901 902 905 906 907 908 910 911 912 914 916 919 921 922 924 927 928 930 932 933 936 937 938 939 940 941 943 945 946 947 951 952 953 956 957 958 960 961 962 963 964 966 967 968 970 971 972 973 974 978 979 980 981 983...

result:

ok 2 lines

Test #19:

score: 15

Accepted

time: 0ms

memory: 8832kb

input:

10000 1000 200
1 2
1 3905
2 3
2 1266
2 1583
2 8609
3 4
3 1168
3 3366
3 3953
3 4186
4 5
4 6117
4 6405
4 9918
5 6
5 1710
5 1990
5 2048
5 3850
6 7
6 1252
6 4357
7 8
7 1527
7 2937
8 9
8 1184
8 3697
9 10
9 1448
9 3100
10 11
10 1285
10 1598
10 7462
11 12
11 3302
12 13
12 1147
12 1859
12 1933
12 1966
12 45...

output:

781
338 342 346 348 351 354 357 359 367 369 373 378 380 381 384 388 391 395 398 399 403 408 409 413 417 420 423 426 430 431 435 437 439 448 450 454 457 460 466 468 472 477 478 480 483 486 492 496 498 500 501 505 507 512 514 520 522 526 529 532 534 537 542 546 549 554 555 556 557 560 566 571 574 578 ...

result:

ok 2 lines

Test #20:

score: 15

Accepted

time: 9ms

memory: 8568kb

input:

10000 1000 10
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 60...

output:

5392
1 5 6 8 12 13 17 20 21 22 23 28 29 31 33 37 42 43 44 46 47 53 54 55 57 58 59 60 61 62 63 66 67 69 71 72 73 74 75 77 78 79 81 82 85 87 89 90 93 94 95 96 97 99 100 101 102 104 106 107 109 113 115 116 117 118 119 123 126 128 129 132 133 135 136 138 139 143 144 145 149 150 151 152 154 155 159 162 1...

result:

ok 2 lines

Test #21:

score: 15

Accepted

time: 9ms

memory: 10752kb

input:

10000 1000 100
1 2
1 8
1 9
1 14
1 18
1 19
1 21
1 23
1 27
1 29
1 31
1 34
1 39
1 42
1 43
1 46
1 50
1 62
1 66
1 69
1 70
1 71
1 72
1 73
1 74
1 78
1 81
1 83
1 86
1 91
1 92
1 94
1 95
1 99
1 100
1 111
1 112
1 113
1 114
1 117
1 120
1 121
1 122
1 123
1 126
1 127
1 129
1 130
1 134
1 139
1 142
1 145
1 150
1 15...

output:

2
1 3340

result:

ok 2 lines

Test #22:

score: 15

Accepted

time: 0ms

memory: 7924kb

input:

output:

5
1 5 6 7 8

result:

ok 2 lines

Test #23:

score: 15

Accepted

time: 0ms

memory: 8732kb

input:

10000 200 20
1 2
1 5
1 12
1 77
1 172
1 184
1 277
1 1766
1 2017
1 4032
2 3
2 11
2 42
2 61
2 222
2 223
2 303
2 330
2 1727
2 2980
2 5126
3 4
3 7
3 8
3 97
3 100
3 305
3 1744
3 5169
3 8096
4 6
4 37
4 218
4 481
4 815
4 1423
4 5620
5 117
5 334
5 398
5 616
5 2003
5 3397
5 3829
5 6029
5 9110
6 9
6 48
6 485
6...

output:

93
1 4 6 11 12 13 22 23 24 31 47 55 64 66 75 86 107 131 133 154 159 168 246 266 299 340 358 387 403 461 465 466 467 468 471 472 473 474 482 517 538 555 560 578 597 787 793 807 913 927 1238 1442 1791 1822 1903 2016 2161 2162 2187 2188 2508 2727 3428 3524 3526 3837 3858 4188 4333 4454 4569 4587 4639 4...

result:

ok 2 lines

Test #24:

score: 15

Accepted

time: 3ms

memory: 10764kb

input:

10000 200 55
1 2
1 3
1 9
1 13
1 14
1 17
1 74
1 106
1 871
1 4418
2 4
2 134
2 148
2 1297
2 1391
2 1547
2 1833
2 3287
2 3737
2 4247
3 6
3 8
3 20
3 83
3 271
3 2372
3 5357
4 5
4 18
4 24
4 27
4 118
4 4039
5 7
5 31
5 47
5 91
5 247
5 378
5 466
5 1118
5 1254
6 11
6 12
6 54
6 75
6 105
6 916
6 4245
6 7621
7 10...

output:

21
1 2 3 11 21 23 24 28 29 30 34 43 70 72 128 142 154 334 480 742 752

result:

ok 2 lines

Test #25:

score: 15

Accepted

time: 1ms

memory: 7940kb

input:

output:

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

result:

ok 2 lines

Test #26:

score: 15

Accepted

time: 1ms

memory: 10116kb

input:

20 10 5
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
4 2 4 7 9
4 3 5 6 7
4 4 5 8 9
4 1 3 6 8
4 2 3 7 8
4 6 8 16 18
4 6 8 16 18
4 6 7 17 19
4 7 8 16 17
4 6 7 16 17

output:

13
4 5 6 7 8 9 10 11 12 13 14 15 16

result:

ok 2 lines

Test #27:

score: 15

Accepted

time: 0ms

memory: 10912kb

input:

10000 450 12
1 2
1 6371
1 7920
2 3
2 6711
3 4
4 5
5 6
5 5456
6 7
6 5201
6 6455
7 8
7 6177
8 9
8 7613
9 10
10 11
11 12
12 13
12 6332
13 14
14 15
15 16
16 17
16 6901
17 18
18 19
18 6549
19 20
19 6090
19 7126
19 8135
20 21
21 22
22 23
22 5263
23 24
24 25
24 5218
25 26
25 6314
25 9287
26 27
27 28
28 29
...

output:

4936
20 22 23 24 25 27 28 30 34 35 36 38 39 41 44 45 46 47 48 51 54 56 58 60 61 62 63 64 65 66 67 79 80 82 83 84 86 87 88 89 90 92 93 94 95 98 100 103 105 110 113 114 116 119 121 122 125 126 127 129 130 131 132 133 134 135 136 137 138 140 142 143 144 146 147 148 151 153 156 158 159 160 161 162 164 1...

result:

ok 2 lines

Test #28:

score: 15

Accepted

time: 3ms

memory: 8764kb

input:

10000 101 2
1 2
1 6504
2 3
2 1733
3 4
3 2417
3 3758
4 5
4 7501
5 6
5 2206
6 7
6 1017
7 8
7 2151
7 9241
8 9
8 1486
8 1635
9 10
9 1408
9 2642
10 11
10 4577
11 12
11 1347
12 13
12 2140
13 14
13 2192
13 6978
14 15
14 4124
15 16
15 1822
15 7890
15 9019
16 17
16 5150
16 6022
17 18
17 1331
17 1960
18 19
18...

output:

448
5 6 8 11 59 60 62 65 77 80 83 87 139 143 145 147 175 176 261 264 274 276 277 282 286 288 290 291 292 294 355 401 403 404 533 534 539 573 640 642 644 646 680 682 685 687 689 690 694 697 698 700 707 778 779 780 781 797 802 803 846 851 852 864 868 871 872 874 895 900 903 904 906 907 909 912 918 923...

result:

ok 2 lines

Test #29:

score: 15

Accepted

time: 3ms

memory: 8752kb

input:

10000 1000 2
1 2
1 3
1 21
1 26
1 45
1 64
1 71
1 79
1 86
1 107
1 117
1 141
1 155
1 156
1 161
1 165
1 174
1 180
1 188
1 196
1 199
1 204
1 215
1 229
1 230
1 242
1 243
1 246
1 258
1 267
1 277
1 314
1 318
1 335
1 351
1 352
1 361
1 369
1 383
1 393
1 401
1 418
1 421
1 423
1 424
1 445
1 454
1 461
1 473
1 47...

output:

183
1 2 69 71 192 219 253 271 298 302 314 353 436 500 591 663 682 701 837 973 1014 1151 1261 1351 1361 1365 1407 1418 1502 1525 1626 1645 1708 1740 1758 1791 1857 1911 2045 2046 2047 2048 2161 2196 2242 2361 2390 2432 2439 2492 2512 2549 2569 2573 2642 2697 2744 2818 3061 3062 3100 3107 3166 3173 31...

result:

ok 2 lines

Test #30:

score: 15

Accepted

time: 3ms

memory: 8892kb

input:

10000 1000 1000
1 2
1 3
1 6
1 11
1 59
1 61
1 69
1 230
1 1247
1 1502
1 1587
1 1990
1 2072
1 2644
1 2922
1 3198
1 3296
1 3599
1 3631
1 3654
1 4435
1 4460
1 4539
1 4697
1 5344
1 5474
1 5595
1 5665
1 6035
1 6126
1 6142
1 6546
1 6690
1 7317
1 7617
1 7742
1 8023
1 8601
1 8782
1 8802
1 8838
1 8992
1 9095
1...

output:

result:

ok single line: '0'

Test #31:

score: 15

Accepted

time: 0ms

memory: 7940kb

input:

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

output:

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

result:

ok 2 lines

Test #32:

score: 15

Accepted

time: 1ms

memory: 7928kb

input:

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

output:

15
1 2 3 4 5 7 9 10 11 12 13 14 15 18 19

result:

ok 2 lines

Test #33:

score: 15

Accepted

time: 1ms

memory: 8032kb

input:

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

output:

13
2 3 5 6 7 8 10 11 12 13 17 18 19

result:

ok 2 lines

Test #34:

score: 15

Accepted

time: 1ms

memory: 10124kb

input:

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

output:

14
1 2 3 4 5 6 8 10 11 13 15 16 17 19

result:

ok 2 lines

Test #35:

score: 15

Accepted

time: 1ms

memory: 10056kb

input:

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

output:

8
2 3 5 7 8 9 11 12

result:

ok 2 lines

Subtask #3:

score: 7

Accepted

Test #36:

score: 7

Accepted

time: 29ms

memory: 20172kb

input:

100000 50000 10000
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 5...

output:

77461
11290 11291 11292 11293 11294 11295 11296 11297 11298 11299 11300 11301 11302 11303 11304 11305 11306 11307 11308 11309 11310 11311 11312 11313 11314 11315 11316 11317 11318 11319 11320 11321 11322 11323 11324 11325 11326 11327 11328 11329 11330 11331 11332 11333 11334 11335 11336 11337 11338 ...

result:

ok 2 lines

Test #37:

score: 7

Accepted

time: 1ms

memory: 10060kb

input:

20 25 12
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
3 5 6 8
3 11 15 16
3 6 7 16
3 3 10 17
3 12 13 14
4 2 5 19 20
4 5 6 18 19
4 4 5 18 19
4 2 6 18 19
4 4 7 18 19
4 5 6 18 20
4 5 6 17 18
4 5 7 19 20
4 5 8 18 20
4 3 4 17 18
4 4 5 6 7
4 4 5 6 7
4 2 3...

output:

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

result:

ok 2 lines

Test #38:

score: 7

Accepted

time: 31ms

memory: 18892kb

input:

100000 50000 20000
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 5...

output:

44891
27596 27597 27598 27599 27600 27601 27602 27603 27604 27605 27606 27607 27608 27609 27610 27611 27612 27613 27614 27615 27616 27617 27618 27619 27620 27621 27622 27623 27624 27625 27626 27627 27628 27629 27630 27631 27632 27633 27634 27635 27636 27637 27638 27639 27640 27641 27642 27643 27644 ...

result:

ok 2 lines

Test #39:

score: 7

Accepted

time: 25ms

memory: 18560kb

input:

100000 50000 30000
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 5...

output:

result:

ok single line: '0'

Test #40:

score: 7

Accepted

time: 25ms

memory: 18616kb

input:

100000 5000 4000
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
...

output:

84308
7834 7835 7836 7837 7838 7839 7840 7841 7842 7843 7844 7845 7846 7847 7848 7849 7850 7851 7852 7853 7854 7855 7856 7857 7858 7859 7860 7861 7862 7863 7864 7865 7866 7867 7868 7869 7870 7871 7872 7873 7874 7875 7876 7877 7878 7879 7880 7881 7882 7883 7884 7885 7886 7887 7888 7889 7890 7891 7892...

result:

ok 2 lines

Test #41:

score: 7

Accepted

time: 32ms

memory: 19596kb

input:

100000 1500 450
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:

95336
2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389...

result:

ok 2 lines

Subtask #4:

score: 29

Accepted

Test #42:

score: 29

Accepted

time: 35ms

memory: 17164kb

input:

100000 50000 50000
1 2
1 62279
2 3
2 65122
2 73814
2 79457
2 80525
3 4
3 84818
3 94649
4 5
4 97078
5 6
6 7
6 91079
7 8
7 86372
8 9
8 61967
9 10
10 11
11 12
11 73785
11 88130
12 13
12 53359
12 95417
13 14
13 99504
14 15
15 16
15 50946
15 51474
16 17
16 59256
16 72237
17 18
18 19
18 63271
19 20
20 21
...

output:

1358
39626 39628 39629 39631 39633 39635 39636 39637 39638 39640 39641 39642 39644 39645 39646 39648 39649 39652 39653 39654 39655 39657 39658 39659 39660 39661 39663 39665 39667 39668 39670 39671 39672 39673 39674 39675 39676 39677 39678 39681 39682 39684 39685 39687 39688 39689 39690 39692 39693 3...

result:

ok 2 lines

Test #43:

score: 29

Accepted

time: 32ms

memory: 13836kb

input:

100000 50000 50000
1 2
1 15517
2 3
3 4
3 5689
3 16979
3 23884
3 46692
4 5
4 40040
4 53822
4 84197
5 6
5 5730
5 6112
5 9968
5 30096
6 7
6 7773
6 22479
6 26336
6 54232
7 8
7 14903
7 23183
7 33836
8 9
8 6240
8 42540
9 10
9 6120
9 7314
9 9921
9 12838
9 34198
9 40794
10 11
10 8363
10 13153
11 12
11 5080
...

output:

812
7814 7819 7823 7831 7833 7836 7839 7842 7844 7850 7852 7856 7863 7866 7871 7876 7882 7888 7892 7899 7904 7907 7911 7913 7917 7922 7927 7934 7942 7945 7947 7952 7955 7960 7963 7965 7970 7974 7978 7982 7986 7993 7996 8000 8005 8007 8010 8016 8022 8025 8033 8036 8039 8044 8048 8053 8059 8061 8066 8...

result:

ok 2 lines

Test #44:

score: 29

Accepted

time: 39ms

memory: 13424kb

input:

100000 50000 50000
1 2
1 3
1 4
1 5
1 6
1 25
1 31
1 202
1 666
1 780
1 3194
1 41093
2 26
2 77
2 117
2 440
2 527
2 1063
2 1867
2 13853
2 15614
3 7
3 8
3 16
3 110
3 225
3 1404
3 2939
3 5271
3 42219
3 77189
4 32
4 109
4 1570
4 1614
4 2456
4 3365
4 7719
4 8233
4 58195
4 87792
5 13
5 19
5 122
5 188
5 350
5...

output:

result:

ok single line: '0'

Test #45:

score: 29

Accepted

time: 35ms

memory: 14160kb

input:

100000 50000 50000
1 2
1 3
1 8
1 10
1 35
1 61
1 74
1 151
1 258
1 453
1 547
1 2551
1 9831
1 13537
2 4
2 6
2 7
2 25
2 31
2 85
2 114
2 230
2 346
2 435
2 436
2 2076
2 2630
2 29441
2 31058
2 45267
3 12
3 98
3 210
3 284
3 510
3 748
3 776
3 7379
3 13801
3 47541
4 5
4 11
4 17
4 18
4 107
4 130
4 140
4 1138
4...

output:

result:

ok single line: '0'

Test #46:

score: 29

Accepted

time: 39ms

memory: 12732kb

input:

100000 50000 50000
1 2
1 10
1 56
1 86
1 881
1 1881
1 9653
1 16330
1 16408
1 79445
2 3
2 14
2 20
2 31
2 83
2 1138
3 4
3 12
3 15
3 23
3 6392
3 29657
3 42013
4 5
4 6
4 13
4 18
4 176
4 5357
4 7236
4 8271
4 15963
4 47479
5 7
5 8
5 39
5 48
5 55
5 590
5 771
5 1364
5 1466
5 2581
5 65537
6 27
6 94
6 125
6 53...

output:

result:

ok single line: '0'

Test #47:

score: 29

Accepted

time: 27ms

memory: 17136kb

input:

100000 50000 50000
1 2
1 53311
2 3
2 54896
3 4
3 65577
3 72775
3 92317
4 5
5 6
6 7
7 8
7 56026
8 9
8 59658
8 95562
9 10
9 59547
10 11
11 12
11 59625
11 82618
12 13
13 14
14 15
15 16
16 17
16 75599
16 80627
17 18
18 19
19 20
20 21
21 22
22 23
22 54774
22 69321
22 88301
23 24
23 52454
23 64331
23 9049...

output:

10462
29573 29575 29576 29577 29578 29582 29586 29587 29588 29589 29591 29593 29595 29596 29599 29601 29602 29603 29605 29607 29608 29609 29610 29611 29612 29615 29616 29617 29618 29620 29621 29622 29623 29624 29625 29626 29627 29628 29631 29634 29635 29637 29638 29640 29642 29643 29645 29646 29647 ...

result:

ok 2 lines

Test #48:

score: 29

Accepted

time: 31ms

memory: 16016kb

input:

100000 50000 50000
1 2
1 98739
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
11 63429
12 13
13 14
13 84602
13 93828
13 94431
14 15
15 16
15 51559
15 91204
15 96091
16 17
17 18
18 19
19 20
20 21
20 58296
21 22
21 68866
22 23
23 24
24 25
24 71090
25 26
26 27
27 28
28 29
29 30
29 93585
30 31
30 99639
31...

output:

5255
16354 16357 16358 16359 16361 16362 16363 16365 16366 16368 16369 16371 16373 16376 16377 16380 16381 16383 16384 16385 16387 16390 16391 16394 16397 16398 16399 16403 16405 16409 16410 16411 16413 16417 16419 16420 16422 16425 16426 16428 16429 16430 16432 16435 16437 16439 16441 16442 16445 1...

result:

ok 2 lines

Subtask #5:

score: 16

Accepted

Dependency #4:

100%

Accepted

Test #49:

score: 16

Accepted

time: 35ms

memory: 17144kb

input:

100000 25100 25100
1 2
2 3
3 4
3 68643
4 5
5 6
5 70418
6 7
6 68653
7 8
8 9
8 89530
9 10
9 84034
9 90061
10 11
10 71209
11 12
11 76160
12 13
13 14
14 15
15 16
15 62077
16 17
17 18
17 60594
18 19
18 51933
19 20
19 69592
20 21
20 65868
21 22
22 23
23 24
23 88081
24 25
25 26
25 50544
25 63077
26 27
27 2...

output:

13534
33918 33922 33924 33925 33926 33927 33929 33931 33932 33933 33934 33935 33936 33938 33939 33940 33941 33944 33946 33947 33949 33951 33952 33954 33956 33958 33959 33960 33961 33962 33965 33967 33969 33971 33972 33974 33976 33979 33980 33981 33982 33983 33984 33986 33988 33989 33991 33992 33994 ...

result:

ok 2 lines

Test #50:

score: 16

Accepted

time: 33ms

memory: 16436kb

input:

100000 25100 25100
1 2
2 3
3 4
3 51084
4 5
5 6
5 65577
6 7
7 8
7 65820
8 9
9 10
9 51566
10 11
11 12
11 89596
12 13
13 14
14 15
14 88558
15 16
16 17
17 18
17 77957
18 19
18 60359
19 20
20 21
20 95036
21 22
22 23
22 77911
22 92900
23 24
23 85587
23 90371
24 25
25 26
25 53283
26 27
26 87836
27 28
27 50...

output:

14213
49644 49646 49648 49650 49651 49653 49655 49656 49657 49658 49660 49661 49662 49663 49665 49666 49667 49670 49672 49674 49676 49679 49680 49682 49683 49684 49685 49687 49689 49690 49691 49692 49693 49694 49695 49697 49698 49699 49700 49702 49705 49706 49709 49712 49713 49716 49718 49719 49721 ...

result:

ok 2 lines

Test #51:

score: 16

Accepted

time: 33ms

memory: 19748kb

input:

100000 600 600
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:

96322
2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529...

result:

ok 2 lines

Test #52:

score: 16

Accepted

time: 33ms

memory: 20024kb

input:

100000 600 600
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:

91388
3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093...

result:

ok 2 lines

Test #53:

score: 16

Accepted

time: 26ms

memory: 13016kb

input:

100000 200 200
1 2
1 3
1 5
1 13
1 18
1 19
1 23
1 28
1 34
1 46
1 73
1 76
1 79
1 81
1 93
1 98
1 130
1 132
1 149
1 165
1 174
1 182
1 198
1 215
1 219
1 221
1 251
1 252
1 255
1 256
1 287
1 294
1 310
1 311
1 313
1 314
1 324
1 334
1 356
1 357
1 358
1 377
1 379
1 381
1 384
1 386
1 407
1 415
1 426
1 428
1 44...

output:

9
1 2 3 9938 9939 39869 39870 49946 60004

result:

ok 2 lines

Test #54:

score: 16

Accepted

time: 30ms

memory: 13152kb

input:

100000 200 200
1 2
1 3
1 5
1 9
1 11
1 13
1 15
1 31
1 33
1 64
1 65
1 70
1 77
1 84
1 94
1 99
1 105
1 106
1 114
1 126
1 143
1 154
1 156
1 162
1 169
1 174
1 185
1 190
1 206
1 211
1 217
1 224
1 227
1 250
1 260
1 268
1 272
1 285
1 290
1 293
1 302
1 316
1 330
1 335
1 336
1 340
1 352
1 368
1 370
1 373
1 393...

output:

9
1 2 3 4 9954 19993 29976 29977 49885

result:

ok 2 lines

Test #55:

score: 16

Accepted

time: 43ms

memory: 13948kb

input:

100000 5000 5000
1 2
1 3
1 4
1 5
1 37
1 50
1 83
1 90
1 135
1 327
1 732
1 828
1 2613
1 5328
1 5562
1 6272
1 6504
1 6805
1 6921
1 14617
2 8
2 58
2 60
2 61
2 76
2 123
2 791
2 2190
2 4555
2 40702
2 89226
2 94768
3 11
3 62
3 93
3 355
3 450
3 2681
3 5214
3 5651
3 5753
3 6219
4 18
4 22
4 42
4 197
4 275
4 4...

output:

10
1 4 21 59 67 68 80 87 88 96

result:

ok 2 lines

Test #56:

score: 16

Accepted

time: 34ms

memory: 14300kb

input:

100000 5000 5000
1 2
1 5
1 7
1 17
1 19
1 74
1 162
1 165
1 396
1 3099
1 14356
1 46403
2 3
2 4
2 6
2 9
2 55
2 56
2 480
2 6657
2 6784
2 70050
3 174
3 822
3 887
3 5593
3 38488
4 27
4 30
4 57
4 7211
4 10300
4 29359
4 52613
4 55406
4 71610
4 76713
4 80366
5 10
5 26
5 36
5 81
5 1376
5 2524
5 3430
5 13591
5...

output:

11
1 2 3 15 16 50 88 149 238 667 940

result:

ok 2 lines

Test #57:

score: 16

Accepted

time: 33ms

memory: 13204kb

input:

100000 50000 50000
1 2
1 4
1 27
1 149
1 258
1 804
1 3050
1 79532
2 3
2 13
2 24
2 41
2 233
2 360
2 744
2 3140
2 6858
3 7
3 8
3 106
3 108
3 366
3 3868
3 49571
4 5
4 9
4 11
4 19
4 25
4 30
4 3625
5 6
5 18
5 58
5 101
5 122
5 126
5 146
5 281
5 450
5 462
5 911
5 1238
5 2375
5 4435
5 44044
5 66908
5 98067
6...

output:

result:

ok single line: '0'

Test #58:

score: 16

Accepted

time: 36ms

memory: 13084kb

input:

100000 50000 50000
1 2
1 26
1 47
1 51
1 176
1 239
1 917
1 17909
1 49346
1 75048
2 3
2 4
2 5
2 28
2 49
2 115
2 586
2 15975
2 94643
3 10
3 45
3 91
3 614
3 867
4 6
4 9
4 14
4 24
4 29
4 33
4 42
4 3277
4 48554
4 98215
5 7
5 8
5 11
5 13
5 81
5 1485
5 2004
5 8006
6 35
6 194
6 909
6 2084
6 20205
6 30588
6 7...

output:

result:

ok single line: '0'

Test #59:

score: 16

Accepted

time: 32ms

memory: 13628kb

input:

100000 50000 50000
1 2
1 6
1 8
1 14
1 33
1 38
1 1457
1 5600
1 14442
1 17440
2 3
2 9
2 10
2 431
2 950
2 1014
2 2632
2 6699
2 9209
2 18242
3 4
3 5
3 27
3 36
3 105
3 296
3 632
3 645
3 2713
3 16771
3 26480
3 31097
3 92668
4 18
4 26
4 864
4 1844
4 2691
4 3341
4 9419
4 10531
4 16079
4 38260
5 22
5 64
5 66...

output:

result:

ok single line: '0'

Test #60:

score: 16

Accepted

time: 38ms

memory: 13816kb

input:

100000 50000 50000
1 2
1 10510
1 11220
2 3
2 16858
2 37622
2 51242
2 66201
2 66308
3 4
3 5656
3 20432
4 5
4 29674
5 6
5 11137
5 19962
5 20203
5 23551
5 26603
6 7
6 5990
6 28883
7 8
7 14780
7 39089
7 47413
8 9
8 12687
9 10
9 11875
9 16221
9 99606
10 11
10 8435
10 17064
10 22645
10 36426
11 12
11 5612...

output:

621
10922 10928 10932 10938 10944 10948 10953 10955 10959 10964 10971 10975 10981 10987 10993 10997 11000 11003 11006 11009 11010 11012 11016 11018 11024 11025 11029 11033 11038 11039 11047 11053 11056 11064 11070 11076 11084 11086 11087 11094 11097 11101 11103 11105 11109 11116 11121 11124 11129 11...

result:

ok 2 lines

Test #61:

score: 16

Accepted

time: 36ms

memory: 15872kb

input:

100000 50000 50000
1 2
2 3
3 4
4 5
5 6
5 88627
6 7
7 8
8 9
9 10
9 54254
10 11
10 79259
11 12
12 13
13 14
13 53367
13 76314
14 15
14 81851
15 16
15 68952
16 17
17 18
17 56544
17 75259
18 19
18 71271
19 20
19 92830
20 21
21 22
22 23
22 80359
23 24
24 25
24 68072
25 26
26 27
27 28
28 29
28 91310
29 30
...

output:

25696
22406 22408 22410 22412 22414 22416 22417 22418 22419 22420 22421 22422 22424 22425 22427 22428 22430 22431 22432 22434 22435 22436 22438 22440 22441 22443 22444 22446 22448 22450 22451 22453 22455 22457 22458 22460 22462 22464 22466 22468 22469 22471 22473 22475 22476 22477 22478 22479 22482 ...

result:

ok 2 lines

Test #62:

score: 16

Accepted

time: 36ms

memory: 16948kb

input:

100000 50000 50000
1 2
2 3
3 4
3 55136
4 5
5 6
6 7
7 8
8 9
8 61011
9 10
9 74144
10 11
10 63500
11 12
12 13
12 66415
13 14
14 15
15 16
16 17
16 71187
17 18
17 69098
18 19
18 88696
19 20
19 50407
20 21
20 95242
21 22
21 76414
22 23
22 89743
23 24
24 25
24 61979
24 80046
25 26
25 74052
26 27
26 53385
2...

output:

36497
15550 15552 15553 15554 15558 15559 15561 15566 15568 15570 15571 15572 15575 15576 15578 15579 15581 15582 15585 15587 15589 15591 15592 15593 15595 15596 15597 15601 15602 15604 15605 15607 15609 15610 15612 15613 15614 15618 15619 15621 15622 15623 15624 15626 15628 15629 15630 15631 15632 ...

result:

ok 2 lines

Test #63:

score: 16

Accepted

time: 33ms

memory: 16988kb

input:

100000 50000 50000
1 2
2 3
3 4
3 61383
4 5
4 58089
5 6
6 7
7 8
7 52230
8 9
8 74353
9 10
10 11
10 73207
11 12
11 65887
11 67659
12 13
12 68989
12 77116
13 14
14 15
15 16
15 79724
16 17
17 18
18 19
19 20
20 21
21 22
21 63863
22 23
23 24
24 25
25 26
25 96936
26 27
26 57474
27 28
27 73808
28 29
29 30
30...

output:

29195
3102 3105 3107 3108 3109 3111 3113 3115 3116 3117 3119 3123 3124 3126 3127 3130 3132 3133 3135 3136 3137 3138 3139 3141 3142 3143 3145 3147 3149 3152 3153 3154 3156 3159 3162 3163 3166 3168 3171 3174 3176 3179 3180 3182 3183 3184 3187 3189 3190 3192 3193 3197 3199 3200 3201 3204 3207 3208 3212...

result:

ok 2 lines

Subtask #6:

score: 25

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Test #64:

score: 25

Accepted

time: 31ms

memory: 16416kb

input:

100000 49998 20000
1 2
2 3
3 4
4 5
4 65852
4 81082
5 6
5 95191
6 7
7 8
8 9
9 10
10 11
11 12
12 13
12 86305
13 14
13 82068
14 15
14 54155
14 90944
15 16
15 90199
16 17
16 72380
16 75437
17 18
18 19
18 63482
19 20
19 72593
20 21
20 51546
21 22
22 23
22 92119
23 24
24 25
25 26
26 27
27 28
27 57345
28 2...

output:

17157
20108 20110 20111 20114 20115 20118 20120 20123 20124 20125 20126 20128 20129 20131 20133 20134 20135 20137 20139 20141 20143 20146 20148 20149 20151 20152 20154 20156 20158 20160 20163 20166 20167 20168 20170 20172 20173 20175 20177 20179 20181 20184 20186 20187 20189 20190 20192 20197 20199 ...

result:

ok 2 lines

Test #65:

score: 25

Accepted

time: 36ms

memory: 12728kb

input:

100000 50000 1000
1 2
1 4
1 23
1 35
1 40
1 81
1 787
1 3423
1 4930
1 93874
2 3
2 5
2 7
2 13
2 54
2 89
2 200
2 4559
2 4877
2 15554
2 50519
2 52091
2 67830
2 85456
2 89689
3 22
3 130
3 181
3 187
3 198
3 724
3 1570
3 2020
3 5295
3 6846
3 9547
3 62657
3 86143
4 10
4 24
4 60
4 763
4 834
4 3371
4 9257
4 52...

output:

92
1 2 4 11 12 13 14 15 26 30 39 40 41 49 51 71 72 83 84 93 94 102 103 111 112 113 114 122 124 130 133 144 154 155 156 164 165 180 181 189 210 222 236 247 248 260 269 287 288 297 302 314 315 322 337 338 363 377 385 403 404 411 412 413 436 437 458 497 502 517 523 524 574 594 640 677 678 680 687 688 6...

result:

ok 2 lines

Test #66:

score: 25

Accepted

time: 50ms

memory: 13152kb

input:

100000 5000 1000
1 2
1 5
1 29
1 38
1 51
1 157
1 246
1 273
1 4286
1 12325
1 23202
1 73660
2 3
2 4
2 7
2 12
2 97
2 215
2 255
2 1442
2 4649
2 6810
2 19954
3 6
3 23
3 84
3 119
3 185
3 232
3 2070
3 4101
3 11089
3 14819
3 15123
4 9
4 15
4 388
4 726
4 3720
4 4179
4 31404
5 14
5 142
5 170
5 204
5 611
5 1243...

output:

86
1 2 4 5 13 14 15 16 18 35 36 42 59 60 61 63 71 72 78 79 88 103 104 110 111 114 115 119 122 126 127 137 145 147 160 161 170 171 198 199 200 213 215 216 217 219 236 237 266 273 274 283 301 322 328 355 366 387 404 414 424 436 457 458 522 537 562 653 751 776 784 787 823 848 851 862 876 891 946 998 10...

result:

ok 2 lines

Test #67:

score: 25

Accepted

time: 42ms

memory: 13664kb

input:

100000 7500 1000
1 2
1 3
1 8
1 25
1 68
1 86
1 5126
1 20584
1 23300
1 48231
1 77482
2 7
2 123
2 229
2 328
2 685
2 1329
2 1878
2 3043
2 3758
2 3818
2 5900
2 24117
2 36816
2 54181
3 4
3 5
3 6
3 10
3 15
3 16
3 21
3 59
3 263
3 3307
3 17879
3 27135
3 42858
3 97850
4 19
4 144
4 173
4 747
4 1880
4 4177
5 9
...

output:

54
1 2 4 12 26 27 28 29 30 33 46 56 58 59 70 84 85 95 102 103 117 125 126 150 151 152 155 179 180 181 208 209 213 221 257 258 259 272 284 288 289 307 309 317 354 355 413 428 454 495 531 829 1058 1341

result:

ok 2 lines

Test #68:

score: 25

Accepted

time: 23ms

memory: 13752kb

input:

100000 1100 200
1 2
1 146
1 240
1 333
1 539
1 541
1 815
1 1006
1 1068
1 1073
1 1082
1 1117
1 1282
1 1455
1 1484
1 1556
1 1697
1 1749
1 1750
1 2029
1 2245
1 2422
1 2958
1 3051
1 3303
1 3378
1 3460
1 3549
1 3613
1 3625
1 3643
1 3805
1 3850
1 3971
1 4177
1 4284
1 4326
1 4493
1 4518
1 4946
1 5318
1 5492...

output:

49
1001 1002 1003 2027 2028 2029 2030 2031 3047 3048 4055 4057 5064 5066 6032 7015 7016 7017 8059 9028 10056 10057 10058 13862 15899 15900 16905 17930 18915 18916 20886 20887 22878 22879 22880 24867 25822 25823 26816 27905 29906 31915 35001 37043 38036 38995 57909 59843 63807

result:

ok 2 lines

Test #69:

score: 25

Accepted

time: 29ms

memory: 13912kb

input:

100000 1100 200
1 2
1 4
1 6
1 9
1 16
1 90
1 271
1 337
1 409
1 490
1 586
1 620
1 872
1 884
1 1052
1 1080
1 1132
1 1525
1 1683
1 1840
1 1920
1 1968
1 2089
1 2244
1 2269
1 2293
1 2306
1 2387
1 2503
1 2633
1 2723
1 2791
1 2841
1 2938
1 2959
1 3025
1 3029
1 3142
1 3153
1 3164
1 3251
1 3271
1 3310
1 3343
...

output:

50
1 2 3 4 5 961 962 1966 1968 2979 4024 4025 4955 5964 5965 5966 6970 7962 7963 7964 10954 11927 12905 14908 15967 17886 20958 21916 25012 25013 25015 25993 27940 29946 29947 34876 34877 35869 36893 40996 42983 43983 43984 43985 46938 49879 49880 52859 73888 80898

result:

ok 2 lines

Test #70:

score: 25

Accepted

time: 31ms

memory: 16768kb

input:

100000 49998 10000
1 2
2 3
2 52949
3 4
4 5
4 89616
5 6
5 63254
6 7
6 68732
7 8
8 9
8 62344
9 10
10 11
10 93255
11 12
11 95698
12 13
12 68231
12 80143
13 14
14 15
14 55801
15 16
16 17
17 18
18 19
19 20
20 21
21 22
21 55378
21 76275
21 79397
22 23
22 86313
23 24
24 25
25 26
25 57170
26 27
27 28
28 29
...

output:

47248
2959 2962 2963 2965 2966 2968 2969 2971 2974 2975 2976 2977 2978 2979 2981 2982 2983 2986 2989 2991 2993 2994 2996 2998 3000 3001 3002 3004 3006 3007 3010 3011 3012 3013 3014 3016 3017 3018 3021 3022 3025 3026 3027 3029 3031 3032 3034 3035 3037 3038 3039 3041 3042 3043 3044 3045 3047 3049 3050...

result:

ok 2 lines

Test #71:

score: 25

Accepted

time: 32ms

memory: 16584kb

input:

100000 26000 10000
1 2
2 3
3 4
3 54313
4 5
4 69684
5 6
6 7
7 8
8 9
9 10
10 11
10 58065
11 12
11 52922
12 13
12 78935
13 14
14 15
14 52401
15 16
15 69110
16 17
17 18
18 19
19 20
19 75810
20 21
21 22
21 78379
22 23
22 61763
23 24
24 25
24 97106
25 26
26 27
26 57079
26 67521
27 28
27 92744
28 29
28 778...

output:

939
16506 16507 16510 16514 16517 16518 16519 16521 16523 16525 16527 16528 16530 16531 16532 16534 16535 16537 16538 16539 16540 16542 16543 16544 16545 16546 16547 16549 16551 16553 16554 16556 16558 16560 16562 16564 16566 16568 16569 16571 16572 16574 16576 16577 16578 16579 16582 16584 16586 16...

result:

ok 2 lines

Test #72:

score: 25

Accepted

time: 1ms

memory: 7932kb

input:

output:

6
3 4 5 6 8 9

result:

ok 2 lines

Test #73:

score: 25

Accepted

time: 4ms

memory: 10616kb

input:

10000 200 20
1 2
1 23
1 95
1 144
1 291
1 886
1 1744
1 6860
2 3
2 10
2 11
2 17
2 24
2 30
2 39
2 45
2 72
2 207
2 230
2 427
2 2611
2 8263
3 4
3 6
3 7
3 13
3 61
3 582
3 2008
4 5
4 48
4 175
4 364
4 855
4 1327
4 3710
5 14
5 31
5 169
5 257
5 980
5 3789
6 8
6 9
6 49
6 506
6 586
6 734
6 3090
6 4302
7 16
7 26...

output:

80
1 3 9 24 25 26 43 44 52 59 71 87 95 96 97 98 126 128 135 146 156 169 178 216 238 260 389 435 495 532 637 649 659 698 709 769 904 1054 1055 1056 1057 1131 1228 1354 1355 1356 1741 1792 1854 2159 2229 2853 3060 3175 3282 3291 3626 3744 4161 4163 4320 4329 4530 5310 5977 5978 6437 6811 6897 7099 711...

result:

ok 2 lines

Test #74:

score: 25

Accepted

time: 0ms

memory: 8780kb

input:

10000 200 55
1 2
1 3
1 6
1 8
1 20
1 37
1 48
1 252
1 3718
1 8400
1 9177
2 5
2 9
2 26
2 27
2 71
2 100
2 124
2 132
2 256
2 938
2 2525
2 3031
3 4
3 70
3 344
3 554
3 1868
3 3508
4 18
4 23
4 30
4 83
4 933
4 1898
5 11
5 58
5 86
5 106
5 283
5 508
5 574
5 1034
5 1590
5 2303
5 2960
5 4838
6 7
6 12
6 47
6 69
6...

output:

17
1 3 4 13 48 49 63 68 69 75 82 92 100 101 276 545 704

result:

ok 2 lines

Test #75:

score: 25

Accepted

time: 1ms

memory: 8076kb

input:

output:

14
4 5 6 7 8 9 10 11 12 13 14 15 16 17

result:

ok 2 lines

Test #76:

score: 25

Accepted

time: 1ms

memory: 7944kb

input:

20 10 5
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
4 3 4 6 7
4 3 4 6 7
4 3 5 6 7
4 3 4 5 6
4 2 3 4 5
4 13 14 16 17
4 13 14 15 17
4 14 15 16 17
4 13 15 16 17
4 12 14 15 17

output:

5
3 4 14 15 16

result:

ok 2 lines

Test #77:

score: 25

Accepted

time: 4ms

memory: 9044kb

input:

10000 450 12
1 2
1 7557
2 3
2 6787
3 4
4 5
4 5818
5 6
6 7
6 6827
6 9427
7 8
8 9
8 6110
9 10
9 8874
10 11
10 9970
11 12
12 13
12 5773
12 7996
13 14
13 7428
14 15
15 16
16 17
17 18
17 8761
18 19
19 20
19 5691
19 5941
19 8529
20 21
20 6888
21 22
21 6555
21 9718
22 23
22 8751
23 24
24 25
25 26
26 27
27 ...

output:

4939
63 64 65 67 69 70 71 72 74 75 76 77 79 81 82 83 84 85 87 88 90 91 93 95 96 97 98 100 102 103 105 108 109 110 111 113 114 115 117 119 120 121 122 123 126 127 128 130 132 133 134 136 137 138 141 142 143 145 146 147 150 151 155 157 159 160 163 164 166 168 170 171 173 174 175 176 177 178 179 181 18...

result:

ok 2 lines

Test #78:

score: 25

Accepted

time: 0ms

memory: 8672kb

input:

10000 101 2
1 2
1 2661
1 5838
1 8997
2 3
2 1682
2 1996
2 4209
3 4
3 1781
3 5204
3 9116
4 5
4 9268
5 6
5 1337
5 2375
5 3328
5 6868
5 9843
6 7
6 2130
6 5324
7 8
7 6215
7 8143
8 9
8 2090
9 10
9 1566
10 11
10 4377
10 4786
10 6187
10 6301
11 12
11 1001
11 1377
11 7989
12 13
12 2212
13 14
13 6376
14 15
14...

output:

515
44 45 46 47 49 60 61 62 66 67 68 71 72 76 77 80 83 122 124 125 128 130 131 132 150 153 155 157 158 159 161 162 163 165 166 169 172 189 194 213 216 218 221 268 271 278 281 282 289 292 313 314 321 327 328 426 430 434 435 439 440 442 443 444 445 453 454 455 525 526 529 530 534 537 539 540 541 544 5...

result:

ok 2 lines

Test #79:

score: 25

Accepted

time: 3ms

memory: 8828kb

input:

10000 1000 2
1 2
1 4
1 5
1 7
1 12
1 17
1 41
1 43
1 46
1 54
1 57
1 84
1 85
1 91
1 98
1 110
1 116
1 119
1 122
1 127
1 138
1 144
1 147
1 161
1 173
1 182
1 185
1 195
1 199
1 211
1 212
1 218
1 228
1 239
1 245
1 283
1 299
1 310
1 347
1 362
1 366
1 404
1 409
1 420
1 435
1 460
1 482
1 485
1 493
1 507
1 513
...

output:

188
1 2 3 4 63 77 92 99 110 119 135 246 257 281 293 385 446 487 499 521 541 544 597 616 741 977 983 990 991 995 1253 1281 1400 1434 1533 1708 1873 1923 2058 2076 2154 2204 2279 2349 2499 2506 2554 2598 2714 2768 2783 2908 2933 3070 3087 3088 3128 3139 3150 3159 3331 3396 3418 3462 3560 3595 3662 375...

result:

ok 2 lines

Test #80:

score: 25

Accepted

time: 0ms

memory: 10668kb

input:

10000 1000 1000
1 2
1 3
1 5
1 10
1 20
1 418
1 798
1 819
1 949
1 1102
1 1298
1 1317
1 1389
1 1458
1 1634
1 1788
1 2144
1 2164
1 2213
1 2218
1 2248
1 2252
1 3347
1 3693
1 3695
1 3716
1 4068
1 4101
1 4920
1 5044
1 5206
1 5327
1 5616
1 6161
1 6567
1 6583
1 6695
1 6790
1 6946
1 6977
1 7128
1 7595
1 7919
...

output:

result:

ok single line: '0'

Test #81:

score: 25

Accepted

time: 1ms

memory: 8068kb

input:

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

output:

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

result:

ok 2 lines

Test #82:

score: 25

Accepted

time: 1ms

memory: 9984kb

input:

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

output:

15
1 2 3 4 5 7 8 9 10 11 14 15 16 17 18

result:

ok 2 lines

Test #83:

score: 25

Accepted

time: 1ms

memory: 9968kb

input:

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

output:

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

result:

ok 2 lines

Test #84:

score: 25

Accepted

time: 0ms

memory: 10064kb

input:

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

output:

13
2 3 4 5 7 8 9 10 11 12 13 16 18

result:

ok 2 lines

Test #85:

score: 25

Accepted

time: 0ms

memory: 8012kb

input:

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

output:

9
1 5 6 8 9 10 11 12 16

result:

ok 2 lines

Test #86:

score: 25

Accepted

time: 13ms

memory: 8584kb

input:

10000 1500 25
1 2
1 3
1 4
1 11
1 12
1 89
1 500
2 20
2 24
2 1877
2 2189
3 5
3 7
3 34
3 59
3 435
3 456
3 3053
3 7548
3 7872
4 8
4 15
4 30
4 54
4 121
4 227
4 241
4 367
4 400
4 3916
4 6187
5 6
5 16
5 29
5 100
5 144
5 571
5 1006
5 1098
5 2534
5 3369
6 10
6 23
6 31
6 37
6 39
6 70
6 91
6 380
6 2805
6 3520
...

output:

1407
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 21 22 23 24 25 26 27 28 29 32 33 34 35 36 40 42 43 44 45 46 48 49 54 55 60 61 62 64 69 70 75 76 77 78 79 80 81 83 85 86 87 88 89 90 91 92 93 94 96 98 99 100 101 102 103 104 106 107 108 109 115 116 120 121 122 123 124 125 126 127 129 130 131 132 135 136 137...

result:

ok 2 lines

Test #87:

score: 25

Accepted

time: 17ms

memory: 10624kb

input:

10000 1500 11
1 2
1 3
1 7
1 10
1 20
1 59
1 64
1 122
1 211
1 635
1 898
1 6145
1 9118
2 4
2 150
2 186
2 574
2 2639
2 3055
3 6
3 8
3 9
3 36
3 1357
3 1643
3 1845
3 3093
3 6497
3 6615
3 6837
4 5
4 18
4 25
4 66
4 96
4 2839
4 7106
5 58
5 69
5 130
5 701
5 846
6 29
6 71
6 76
6 97
6 169
6 175
6 487
6 564
6 65...

output:

3906
1 2 3 4 5 6 7 8 9 10 14 15 16 17 18 20 21 22 23 24 26 31 32 33 34 35 36 38 39 40 41 42 43 45 46 47 48 49 50 52 53 54 57 59 60 62 64 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84 85 86 87 88 91 92 93 94 96 97 98 99 100 103 104 105 106 107 108 109 110 113 114 115 116 117 118 119 120 122 123 ...

result:

ok 2 lines

Test #88:

score: 25

Accepted

time: 12ms

memory: 8788kb

input:

10000 1500 5
1 2
1 6
1 7
1 10
1 448
1 1003
1 1567
1 4201
2 3
2 19
2 327
2 828
3 4
3 29
3 30
3 161
3 356
3 1093
3 3326
3 3537
3 4133
3 8830
4 5
4 45
4 234
4 1577
4 3064
5 11
5 25
5 845
5 2117
6 32
6 41
6 190
6 4995
6 6028
7 8
7 192
7 291
7 763
7 882
7 3183
7 7945
8 9
8 16
8 27
8 46
8 124
8 360
8 460
...

output:

6854
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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 80 81 82 84 85 86 87 88 89 90 92 93 94 95 96 97 98 99 100 101 102 103 104...

result:

ok 2 lines

Test #89:

score: 25

Accepted

time: 0ms

memory: 8960kb

input:

10000 1991 399
1 2
1 7468
2 3
3 4
4 5
5 6
5 8691
6 7
7 8
8 9
9 10
9 8836
9 8871
10 11
10 8183
10 9013
11 12
12 13
13 14
13 9168
14 15
14 8602
15 16
16 17
17 18
18 19
18 9383
19 20
19 8316
20 21
20 9481
21 22
22 23
22 5450
22 7255
23 24
24 25
24 8404
25 26
26 27
27 28
28 29
29 30
29 6782
30 31
30 544...

output:

3233
1379 1381 1382 1383 1386 1387 1389 1391 1392 1393 1394 1397 1401 1402 1403 1404 1405 1407 1410 1411 1413 1414 1417 1421 1422 1424 1426 1427 1429 1431 1433 1434 1435 1437 1440 1441 1442 1445 1448 1449 1450 1452 1453 1454 1456 1458 1460 1462 1463 1464 1465 1466 1467 1469 1471 1474 1475 1476 1477 ...

result:

ok 2 lines

Test #90:

score: 25

Accepted

time: 4ms

memory: 8788kb

input:

10000 1000 200
1 2
1 1627
1 2135
1 8734
2 3
2 3110
2 4217
3 4
3 1844
3 2977
3 8671
4 5
4 4845
4 9505
5 6
5 1374
5 1515
5 8515
6 7
6 1521
6 8499
7 8
7 1169
7 1993
7 2246
7 3924
7 5516
7 7851
7 8560
8 9
8 1525
8 3953
9 10
9 2190
10 11
10 1022
10 1784
11 12
12 13
12 2131
12 2511
13 14
14 15
15 16
15 16...

output:

792
401 405 408 409 414 416 423 428 430 434 437 441 445 448 451 454 456 463 467 468 471 476 481 483 489 492 496 503 506 511 515 517 519 522 523 525 527 534 537 539 544 545 546 550 554 558 562 564 566 568 570 573 578 580 582 586 587 590 593 596 599 604 607 608 611 615 616 621 628 630 637 639 643 646 ...

result:

ok 2 lines

Test #91:

score: 25

Accepted

time: 6ms

memory: 8512kb

input:

10000 1000 10
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 60...

output:

5402
2 3 6 7 8 9 10 11 12 13 14 15 20 21 23 24 25 26 27 28 30 34 35 37 38 39 41 42 48 49 52 54 57 58 59 60 62 63 64 66 68 69 70 71 72 73 76 77 83 84 87 88 92 95 97 106 109 110 111 112 114 115 117 120 122 124 125 126 127 132 133 134 137 144 145 146 147 150 158 159 167 168 170 172 173 175 179 182 183 ...

result:

ok 2 lines

Test #92:

score: 25

Accepted

time: 8ms

memory: 10788kb

input:

10000 1000 100
1 2
1 3
1 5
1 7
1 8
1 10
1 12
1 13
1 14
1 18
1 27
1 35
1 37
1 38
1 39
1 46
1 48
1 54
1 55
1 57
1 60
1 62
1 64
1 68
1 73
1 75
1 78
1 88
1 91
1 92
1 97
1 100
1 101
1 102
1 107
1 109
1 111
1 115
1 122
1 126
1 129
1 130
1 134
1 136
1 145
1 147
1 148
1 151
1 154
1 155
1 156
1 159
1 162
1 1...

output:

2
1 2

result:

ok 2 lines

Test #93:

score: 25

Accepted

time: 1ms

memory: 7944kb

input:

20 25 12
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
3 2 18 20
3 6 13 19
3 6 12 14
3 5 9 17
3 3 9 14
4 4 7 10 13
4 5 7 10 11
4 5 7 9 12
4 3 6 11 12
4 5 6 11 13
4 4 5 10 11
4 3 6 10 11
4 4 6 10 11
4 6 9 11 13
4 6 7 10 12
4 2 3 4 5
4 2 3 4 6
4 1 2 3...

output:

8
3 4 5 6 7 8 9 10

result:

ok 2 lines

Test #94:

score: 25

Accepted

time: 32ms

memory: 20240kb

input:

100000 50000 10000
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 5...

output:

77478
11318 11319 11320 11321 11322 11323 11324 11325 11326 11327 11328 11329 11330 11331 11332 11333 11334 11335 11336 11337 11338 11339 11340 11341 11342 11343 11344 11345 11346 11347 11348 11349 11350 11351 11352 11353 11354 11355 11356 11357 11358 11359 11360 11361 11362 11363 11364 11365 11366 ...

result:

ok 2 lines

Test #95:

score: 25

Accepted

time: 29ms

memory: 19564kb

input:

100000 50000 20000
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 5...

output:

44212
28025 28046 28048 28049 28050 28051 28052 28053 28054 28055 28056 28057 28058 28059 28060 28061 28062 28063 28064 28065 28066 28067 28068 28069 28070 28071 28072 28073 28074 28075 28076 28077 28078 28079 28080 28081 28082 28083 28084 28085 28086 28087 28088 28089 28090 28091 28092 28093 28094 ...

result:

ok 2 lines

Test #96:

score: 25

Accepted

time: 22ms

memory: 19944kb

input:

100000 50000 30000
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 5...

output:

result:

ok single line: '0'

Test #97:

score: 25

Accepted

time: 36ms

memory: 19440kb

input:

100000 5000 4000
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
...

output:

84377
7834 7835 7836 7837 7838 7839 7840 7841 7842 7843 7844 7845 7846 7847 7848 7849 7850 7851 7852 7853 7854 7855 7856 7857 7858 7859 7860 7861 7862 7863 7864 7865 7866 7867 7868 7869 7870 7871 7872 7873 7874 7875 7876 7877 7878 7879 7880 7881 7882 7883 7884 7885 7886 7887 7888 7889 7890 7891 7892...

result:

ok 2 lines

Test #98:

score: 25

Accepted

time: 39ms

memory: 19628kb

input:

100000 1500 450
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:

95312
2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523...

result:

ok 2 lines

Test #99:

score: 25

Accepted

time: 34ms

memory: 13208kb

input:

100000 50000 50000
1 2
1 3
1 5
1 7
1 13
1 43
1 46
1 107
1 241
1 469
1 5266
1 9036
1 39661
1 41928
2 8
2 14
2 100
2 244
2 10994
2 13442
2 30177
2 65336
3 4
3 6
3 87
3 112
3 724
3 1813
3 60565
4 15
4 314
4 744
4 853
4 5086
4 11009
4 33507
4 40779
4 43406
5 26
5 36
5 364
5 429
5 1225
5 1236
5 6048
5 11...

output:

result:

ok single line: '0'

Test #100:

score: 25

Accepted

time: 37ms

memory: 14112kb

input:

100000 50000 50000
1 2
1 4
1 15
1 72
1 1966
1 2020
1 4284
1 6451
1 59780
2 3
2 17
2 2029
2 14257
2 47475
2 75351
3 5
3 79
3 109
3 257
3 313
3 486
3 2038
3 2207
3 2933
3 5557
4 6
4 7
4 12
4 18
4 42
4 188
4 686
4 689
4 765
4 8264
4 13767
4 14915
4 28473
4 30380
4 31485
4 90341
5 10
5 13
5 16
5 47
5 49...

output:

result:

ok single line: '0'

Test #101:

score: 25

Accepted

time: 40ms

memory: 13192kb

input:

100000 50000 50000
1 2
1 4
1 5
1 62
1 63
1 153
1 873
1 968
1 2576
1 55997
1 78808
2 3
2 6
2 8
2 44
2 90
2 109
2 204
2 205
2 1267
2 2619
2 6297
2 11466
3 12
3 14
3 192
3 213
3 347
3 3239
3 10702
3 14589
3 67574
3 92087
4 7
4 34
4 273
4 402
4 1066
4 2415
4 2557
4 5551
5 9
5 15
5 16
5 2111
5 44473
5 44...

output:

result:

ok single line: '0'

Test #102:

score: 25

Accepted

time: 37ms

memory: 14120kb

input:

100000 50000 50000
1 2
1 21194
1 55065
2 3
2 6061
2 8909
2 29301
2 30688
2 81877
2 92316
3 4
3 6252
3 16297
3 18762
4 5
4 12992
4 19686
4 24215
5 6
5 39364
6 7
6 9703
6 23746
6 47953
7 8
7 17950
7 44122
7 79776
8 9
8 7277
8 8759
8 10820
8 53169
9 10
9 5798
9 8416
9 35477
9 62999
10 11
10 7785
10 840...

output:

190
19097 19102 19104 19109 19114 19116 19121 19123 19124 19127 19129 19130 19137 19144 19146 19148 19151 19154 19159 19166 19170 19174 19180 19185 19188 19193 19194 19202 19203 19209 19211 19214 19219 19223 19229 19232 19234 19236 19239 19241 19249 19252 19256 19259 19262 19268 19271 19273 19277 19...

result:

ok 2 lines

Test #103:

score: 25

Accepted

time: 28ms

memory: 15924kb

input:

100000 50000 50000
1 2
1 96275
2 3
3 4
3 78187
4 5
5 6
5 69022
6 7
6 51804
7 8
7 57362
7 80822
8 9
8 76410
8 81647
9 10
10 11
10 59801
10 82367
11 12
12 13
13 14
14 15
15 16
16 17
16 62884
17 18
17 65553
17 80328
18 19
19 20
19 97200
20 21
20 68223
20 70714
21 22
21 74611
21 91950
21 96694
22 23
23 ...

output:

5880
60160 60161 60162 60163 60164 60166 60168 60170 60171 60174 60176 60180 60181 60183 60187 60189 60190 60192 60193 60195 60196 60198 60199 60200 60201 60203 60205 60207 60208 60209 60210 60212 60214 60216 60218 60219 60220 60221 60223 60225 60227 60229 60231 60234 60235 60236 60237 60238 60240 6...

result:

ok 2 lines

Test #104:

score: 25

Accepted

time: 36ms

memory: 16064kb

input:

100000 50000 50000
1 2
1 78037
1 82941
2 3
2 69468
2 90910
3 4
4 5
4 65205
4 84782
5 6
6 7
7 8
8 9
9 10
9 61961
10 11
10 53478
11 12
11 87184
12 13
13 14
14 15
15 16
15 54442
15 69503
15 81471
16 17
17 18
17 53625
18 19
19 20
20 21
21 22
21 88508
22 23
23 24
24 25
24 55016
25 26
25 76485
25 76927
26...

output:

32800
12900 12904 12905 12908 12909 12912 12914 12917 12918 12920 12921 12922 12923 12924 12927 12930 12932 12933 12934 12936 12937 12938 12940 12941 12943 12946 12947 12949 12950 12953 12954 12956 12960 12963 12964 12965 12967 12968 12969 12970 12971 12975 12976 12979 12980 12984 12985 12988 12989 ...

result:

ok 2 lines

Test #105:

score: 25

Accepted

time: 34ms

memory: 17348kb

input:

100000 50000 50000
1 2
1 65520
2 3
2 80957
3 4
3 92074
3 99827
4 5
5 6
6 7
6 52196
6 61773
6 80243
7 8
7 60843
8 9
9 10
9 99574
10 11
10 74235
11 12
12 13
13 14
13 83236
14 15
15 16
15 61546
15 66414
15 70386
16 17
17 18
18 19
18 88802
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
27 83412
2...

output:

2297
51719 51722 51724 51725 51727 51728 51730 51732 51734 51735 51736 51738 51739 51745 51746 51748 51750 51752 51753 51755 51756 51757 51759 51760 51761 51762 51763 51764 51766 51767 51768 51769 51771 51772 51773 51776 51779 51781 51782 51784 51789 51791 51792 51794 51796 51798 51800 51802 51804 5...

result:

ok 2 lines

Test #106:

score: 25

Accepted

time: 35ms

memory: 15984kb

input:

100000 25100 25100
1 2
1 67351
2 3
2 62313
3 4
3 93415
3 96521
4 5
4 77464
4 92348
4 94592
5 6
6 7
7 8
8 9
9 10
10 11
10 75583
11 12
12 13
13 14
13 77921
13 80626
13 97478
14 15
15 16
15 59663
16 17
17 18
17 59906
18 19
19 20
19 70427
20 21
20 59823
21 22
21 86104
22 23
23 24
23 52075
24 25
25 26
26...

output:

23106
10643 10646 10651 10654 10656 10657 10658 10659 10660 10661 10663 10664 10669 10670 10672 10674 10678 10679 10680 10682 10683 10686 10687 10688 10690 10692 10695 10696 10699 10702 10703 10704 10706 10709 10711 10712 10713 10714 10716 10718 10719 10720 10721 10722 10723 10724 10725 10726 10729 ...

result:

ok 2 lines

Test #107:

score: 25

Accepted

time: 35ms

memory: 17504kb

input:

100000 25100 25100
1 2
2 3
2 56230
3 4
3 84720
4 5
4 58848
4 95193
5 6
5 50436
5 90832
6 7
6 86307
7 8
8 9
9 10
10 11
11 12
11 63731
12 13
12 53141
13 14
13 53268
14 15
14 88589
15 16
15 70414
16 17
17 18
17 53642
18 19
19 20
19 66943
20 21
21 22
22 23
22 58469
22 63598
23 24
23 70242
24 25
25 26
25...

output:

9784
12980 12982 12985 12987 12989 12991 12992 12993 12994 12995 12999 13000 13002 13004 13006 13009 13011 13012 13015 13016 13017 13020 13022 13023 13025 13026 13027 13028 13030 13033 13034 13035 13037 13039 13042 13043 13045 13046 13048 13050 13052 13054 13056 13057 13058 13059 13060 13061 13062 1...

result:

ok 2 lines

Test #108:

score: 25

Accepted

time: 33ms

memory: 19444kb

input:

100000 600 600
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:

95697
1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672...

result:

ok 2 lines

Test #109:

score: 25

Accepted

time: 29ms

memory: 20060kb

input:

100000 600 600
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:

94194
2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375...

result:

ok 2 lines

Test #110:

score: 25

Accepted

time: 30ms

memory: 13080kb

input:

100000 200 200
1 2
1 3
1 6
1 8
1 30
1 50
1 78
1 81
1 84
1 89
1 95
1 97
1 103
1 108
1 111
1 124
1 137
1 159
1 162
1 163
1 168
1 188
1 193
1 194
1 195
1 201
1 215
1 227
1 239
1 242
1 245
1 259
1 260
1 279
1 281
1 286
1 290
1 292
1 297
1 303
1 307
1 353
1 354
1 355
1 358
1 364
1 365
1 387
1 411
1 429
1...

output:

9
1 2 3 4 9984 19929 19930 29865 40029

result:

ok 2 lines

Test #111:

score: 25

Accepted

time: 24ms

memory: 13244kb

input:

100000 200 200
1 2
1 3
1 5
1 15
1 24
1 36
1 39
1 47
1 80
1 83
1 98
1 107
1 111
1 133
1 140
1 145
1 154
1 157
1 168
1 179
1 190
1 209
1 235
1 260
1 267
1 272
1 276
1 279
1 294
1 296
1 307
1 321
1 327
1 339
1 341
1 352
1 357
1 363
1 370
1 384
1 387
1 393
1 398
1 401
1 416
1 421
1 424
1 430
1 433
1 440...

output:

9
1 2 3 10049 10050 10051 10052 19951 40098

result:

ok 2 lines

Test #112:

score: 25

Accepted

time: 43ms

memory: 12976kb

input:

100000 5000 5000
1 2
1 4
1 6
1 9
1 15
1 137
1 172
1 8365
2 3
2 5
2 23
2 83
2 160
2 724
2 2067
2 4509
2 17804
2 24222
2 43953
2 60697
3 10
3 19
3 29
3 37
3 61
3 133
3 402
3 414
3 5257
3 12154
3 17339
3 27234
4 8
4 12
4 16
4 22
4 42
4 89
4 704
4 1225
4 2861
4 6447
5 25
5 77
5 125
5 317
5 4257
5 13264
...

output:

5
1 2 3 9 53

result:

ok 2 lines

Test #113:

score: 25

Accepted

time: 39ms

memory: 13204kb

input:

100000 5000 5000
1 2
1 6
1 36
1 39
1 60
1 88
1 204
1 1527
1 3211
1 6738
1 39852
1 44353
2 3
2 4
2 5
2 26
2 210
3 51
3 79
3 171
3 275
3 278
3 983
3 1975
3 4057
3 8339
3 13306
3 27291
4 7
4 27
4 29
4 31
4 32
4 64
4 644
4 2979
4 8408
4 13891
5 44
5 631
5 11908
6 8
6 9
6 10
6 13
6 1933
6 3611
6 27799
6 ...

output:

18
1 2 13 14 16 29 44 51 77 88 129 130 144 149 188 207 301 384

result:

ok 2 lines