QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464781#7895. Graph Partitioning 2Andyqian7AC ✓1168ms427996kbC++202.8kb2024-07-06 14:52:452024-07-06 14:52:46

Judging History

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

  • [2024-07-06 14:52:46]
  • 评测
  • 测评结果:AC
  • 用时:1168ms
  • 内存:427996kb
  • [2024-07-06 14:52:45]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int MAX = 1e5 + 10, mod = 998244353;
int T, n, k, sz[MAX], cnt[MAX], dp[MAX][1010];
vector<int> nei[MAX], sons[MAX];
unordered_map<int, int> dp2[MAX];
void getsz(int s)
{
    sz[s] = 1;
    for (int son : nei[s])
    {
        if (sz[son])
            continue;
        sons[s].pb(son);
        getsz(son);
        sz[s] += sz[son];
    }
}
void dfs(int s)
{
    dp[s][1] = 1;
    int size = 1;
    for (int son : sons[s])
    {
        dfs(son);
        for (int i = min(k + 1, size); i > 0; i--)
        {
            for (int j = min(k + 1, sz[son]); j > 0; j--)
            {
                if (i + j <= k + 1)
                {
                    dp[s][i + j] = (dp[s][i + j] + 1ll * dp[s][i] * dp[son][j]) % mod;
                }
            }
            dp[s][i] = 1ll * dp[s][i] * dp[son][0] % mod;
        }
        size += sz[son];
    }
    if (k + 1 <= size)
        dp[s][0] = (dp[s][k] + dp[s][k + 1]) % mod;
    else if (k <= size)
    {
        dp[s][0] = dp[s][k];
    }
}
void dfs2(int s)
{
    dp2[s][1] = 1;
    for (int son : sons[s])
    {
        dfs2(son);
        unordered_map<int, int> tmp;
        for (auto i : dp2[s])
        {
            for (auto j : dp2[son])
            {
                if (i.first + j.first <= k + 1)
                    tmp[i.first + j.first] = (tmp[i.first + j.first] + 1ll * i.second * j.second) % mod;
            }
        }
        dp2[s] = tmp;
    }
    if (dp2[s].count(k))
        dp2[s][0] = (dp2[s][0] + dp2[s][k]) % mod;
    if (dp2[s].count(k + 1))
        dp2[s][0] = (dp2[s][0] + dp2[s][k + 1]) % mod;
}
int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        if (k < 1000)
        {
            for (int i = 0; i < n - 1; i++)
            {
                int u, v;
                cin >> u >> v;
                nei[u].pb(v), nei[v].pb(u);
            }
            getsz(1), dfs(1);
            cout << dp[1][0] << endl;
            for (int i = 1; i <= n; i++)
            {
                sz[i] = 0;
                nei[i].clear(), sons[i].clear();
                for (int j = 0; j <= k + 1; j++)
                {
                    dp[i][j] = 0;
                }
            }
        }
        else
        {
            for (int i = 0; i < n - 1; i++)
            {
                int u, v;
                cin >> u >> v;
                nei[u].pb(v), nei[v].pb(u);
            }
            getsz(1), dfs2(1);
            cout << dp2[1][0] << endl;
            for (int i = 1; i <= n; i++)
            {
                sz[i] = 0;
                nei[i].clear(), sons[i].clear(), dp2[i].clear();
            }
        }
    }
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 13464kb

input:

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

output:

2
1

result:

ok 2 lines

Test #2:

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

input:

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

output:

0
3
112
0
1
0
1
0
0
0
1
0
1
0
0
1
0
140
0
0
0
814
1
6
1
1
2
2
0
612
0
1
0
0
0
1
1
0
0
121
4536
0
0
1718
0
0
1
0
444
1
1908
1813
3
74
0
1
0
46
0
0
0
0
0
0
0
0
0
1
0
1
1
1
239
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
48
0
2
0
0
0
1
364
0
206
0
0
76
0
1
0
0
2
0
1
2
0
0
1
0
0
4
0
1
1
0
0
1
1
1
0
0
1
1
...

result:

ok 5550 lines

Test #3:

score: 0
Accepted
time: 481ms
memory: 414964kb

input:

3
99990 259
23374 69108
82204 51691
8142 67119
48537 97966
51333 44408
33147 68485
21698 86824
15746 58746
78761 86975
58449 61819
69001 68714
25787 2257
25378 14067
64899 68906
29853 31359
75920 85420
76072 11728
63836 55505
43671 98920
77281 25176
40936 66517
61029 61440
66908 52300
92101 59742
69...

output:

259200
247
207766300

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 597ms
memory: 414508kb

input:

3
99822 332
11587 83046
63424 60675
63423 73718
74622 40130
5110 26562
28361 80899
30886 70318
8708 11068
34855 96504
7904 75735
31904 42745
87892 55105
82374 81319
77407 82147
91475 12343
13470 95329
58766 95716
83232 44156
75907 92437
69785 93598
47857 33018
62668 31394
24238 72675
98254 43583
180...

output:

315881300
4505040
185631154

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 445ms
memory: 34532kb

input:

3
99021 1000
41739 4318
72541 76341
31227 15416
49232 13808
50837 51259
74464 11157
92684 84646
95226 64673
74155 82511
33301 31373
5901 29318
38227 98893
96752 57411
35167 42401
24344 90803
6956 33753
51120 24535
29594 2646
70305 32961
93079 38070
49273 48987
62799 77986
94353 84447
74970 31546
263...

output:

917568
1
1213

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 379ms
memory: 33656kb

input:

3
100000 10000
15556 26349
14984 68012
43040 63434
32168 60646
70509 38559
26238 29031
45952 19431
29510 54395
5676 59515
28220 41438
46902 56640
8221 80059
77225 66558
17473 87324
20819 35098
29515 12641
84108 41157
11223 66562
25999 95852
3790 63605
20963 15799
217 58841
61619 13324
3406 60525
693...

output:

1
1
1

result:

ok 3 lines

Test #7:

score: 0
Accepted
time: 546ms
memory: 425896kb

input:

3
99969 79
84806 29026
76190 49303
81448 88606
47775 83229
7424 30063
75504 59640
28456 18012
26623 18383
66305 32640
55981 65140
25760 523
76248 13482
25598 55231
96844 17032
44892 64592
4915 50521
49879 86466
99286 20894
97915 76337
38424 2546
17489 46475
91791 2636
79283 35209
14773 60224
94096 5...

output:

855988479
413863362
390147247

result:

ok 3 lines

Test #8:

score: 0
Accepted
time: 844ms
memory: 424916kb

input:

3
99655 347
11149 99084
14300 87239
74978 75669
48703 12705
62600 62372
85743 67544
11248 36566
31920 23357
91970 67460
47599 56467
67521 16526
50284 63800
6701 3456
15660 81507
43192 5734
57965 67731
42676 26195
60309 19848
30504 47635
66455 98017
1645 70119
47861 95592
32453 39251
31178 59516
2144...

output:

500906609
4366296
91620762

result:

ok 3 lines

Test #9:

score: 0
Accepted
time: 1168ms
memory: 150008kb

input:

3
99074 1000
10018 10926
93276 10882
57018 36456
36298 20551
34971 14671
82296 41279
49459 20897
56874 98633
57849 24888
15425 8116
62887 30467
61380 38308
70548 49238
49287 13456
83286 31072
93096 52396
17509 64864
75106 13508
26188 61092
74762 46749
78773 89071
57494 24130
29618 24192
21061 11372
...

output:

895874645
85900584
237336

result:

ok 3 lines

Test #10:

score: 0
Accepted
time: 557ms
memory: 51348kb

input:

3
90006 10000
73490 30293
71611 45400
5985 73192
89192 86831
26722 13580
73 42029
64900 69699
1501 9326
5417 72489
81756 62830
19449 20243
85297 63347
30952 20243
69122 148
42880 88227
69343 66867
72919 75705
53663 32672
65715 35962
19421 5905
13102 4284
40894 88911
87558 21940
82573 82415
83203 131...

output:

84
3
1

result:

ok 3 lines

Test #11:

score: 0
Accepted
time: 503ms
memory: 421180kb

input:

3
99923 88
78033 17440
86489 72898
41036 84474
8561 18775
31676 62859
379 69955
66435 12651
7678 88259
64810 65776
30805 95902
81241 9085
22021 14554
26753 64229
59137 92000
90432 10825
80094 9597
7911 60599
66954 99719
81996 99136
42256 88131
73137 65163
97771 99132
66272 25651
80912 42272
94725 75...

output:

578738252
635410385
616515379

result:

ok 3 lines

Test #12:

score: 0
Accepted
time: 832ms
memory: 423900kb

input:

3
99773 362
16637 83914
63631 58741
27359 60161
8952 80795
52395 54853
26443 41008
37319 45707
47426 17039
26219 59547
19137 49086
14972 25115
76069 24037
26972 72363
92135 98301
86774 59913
54636 40038
88922 39806
62589 40377
94667 83663
23634 79618
24932 51069
15632 14476
73182 42535
98053 50141
2...

output:

718699462
887216138
726376429

result:

ok 3 lines

Test #13:

score: 0
Accepted
time: 904ms
memory: 107720kb

input:

3
99092 1000
49588 46079
55304 73177
18967 13059
52465 87314
78600 97324
69426 93208
93660 32936
1196 14888
79251 2603
82306 14847
7113 64862
2219 96349
68128 70861
42412 26436
3256 55313
13458 61469
6266 41279
75057 19685
88624 5001
3437 60451
32605 41073
72888 60159
26888 14135
18572 17170
11099 4...

output:

495088901
243801881
33

result:

ok 3 lines

Test #14:

score: 0
Accepted
time: 465ms
memory: 44736kb

input:

3
90000 10000
87964 18251
12687 18104
78011 37556
4983 29905
11284 20403
34250 81402
89508 6978
62519 18650
87412 74628
86526 88800
36368 38274
60311 25701
31660 13827
19031 84677
12557 49159
78925 43858
11560 86110
26994 87734
858 46385
85867 29897
62594 20009
50471 87109
77717 8190
71331 44932
570...

output:

1
1
1

result:

ok 3 lines

Test #15:

score: 0
Accepted
time: 685ms
memory: 421564kb

input:

3
99819 218
15128 87625
26894 97807
74349 83371
14774 10443
13261 31540
78090 53944
58055 19995
63820 64481
269 89813
80310 31087
98842 24345
32620 10612
58004 41547
86990 99489
8873 50122
9750 9895
16330 58033
72917 46097
90881 12042
98057 49196
17548 87122
66574 96602
36023 19215
19515 43934
14875...

output:

880185860
949287013
157116569

result:

ok 3 lines

Test #16:

score: 0
Accepted
time: 706ms
memory: 423892kb

input:

3
99675 377
85617 1008
16957 5302
29036 43568
26644 73742
95538 87850
36434 95180
75521 95557
61327 7435
14918 15313
56136 58622
64335 13941
50507 27180
78582 32465
6420 87514
90207 73441
42230 45679
5442 18048
58968 83147
65534 19505
60549 90524
55605 21274
93589 24952
73182 3136
27000 73554
2566 8...

output:

789159485
532394394
26715

result:

ok 3 lines

Test #17:

score: 0
Accepted
time: 564ms
memory: 103400kb

input:

3
99044 1000
76852 50370
30397 85586
92739 11074
76934 75240
37614 64349
77982 12307
73391 93804
83432 22135
73239 9997
10638 54120
4067 97619
83197 70602
96104 2925
10203 7199
78302 40626
31063 42976
78481 25765
19133 81706
21489 82284
37017 30262
71614 56388
30698 37348
57013 68118
17186 50664
655...

output:

96984968
57966928
37401

result:

ok 3 lines

Test #18:

score: 0
Accepted
time: 214ms
memory: 53448kb

input:

3
90007 10000
34002 29711
67960 67913
37266 81420
31618 89748
31937 80647
15048 29012
39472 5346
66976 79828
13310 82211
27879 13150
80096 22971
42896 29977
31648 66746
58037 28226
81556 35007
50862 86637
47666 17507
72347 72849
36790 16145
41695 66392
9514 77718
37806 29200
61221 81716
26864 27272
...

output:

13
1
1

result:

ok 3 lines

Test #19:

score: 0
Accepted
time: 265ms
memory: 425504kb

input:

3
99999 1
15526 5816
15526 91340
85090 15526
1815 15526
15526 60171
60385 15526
69663 15526
15526 41953
53736 15526
89414 15526
15526 94460
21625 15526
15526 8540
15526 67534
15526 4622
15526 7978
15526 28610
42253 15526
15526 26283
2628 15526
15526 5188
15526 6704
15526 69277
15526 51976
15526 7295...

output:

99999
0
0

result:

ok 3 lines

Test #20:

score: 0
Accepted
time: 582ms
memory: 413496kb

input:

3
100000 429
1 57398
57398 57200
76340 1
76340 59785
76340 84657
1 26989
88056 26989
26989 4041
26989 36411
1 61120
61120 73590
52743 61120
61120 72023
19959 61120
44366 1
9930 44366
41401 44366
51704 44366
21854 44366
1 12768
12768 2694
12768 40037
12768 31800
12768 46496
1 31963
85737 31963
31963 ...

output:

0
0
0

result:

ok 3 lines

Test #21:

score: 0
Accepted
time: 400ms
memory: 212768kb

input:

6
50000 267
1 34009
1 16272
16272 47288
1 35559
35559 15885
1 6564
27858 6564
22579 6564
1 44936
17220 44936
26160 44936
1 32316
35365 32316
37958 32316
20510 1
27878 20510
9368 20510
33467 20510
26290 1
48832 26290
24415 26290
2851 26290
1 12040
21167 12040
36738 12040
12040 7284
1 12936
12936 2982...

output:

0
0
0
0
0
0

result:

ok 6 lines

Test #22:

score: 0
Accepted
time: 347ms
memory: 113612kb

input:

12
25000 258
13484 1
1 16801
16801 7731
1 13880
13880 79
13880 6939
5802 13880
11343 1
21799 11343
6193 11343
8976 11343
11343 15462
9279 1
22367 9279
1419 9279
1412 9279
23782 9279
1 6728
6728 18671
6728 20942
6728 16877
16191 6728
6728 20618
3948 1
3948 16740
3948 24198
3948 85
3948 4865
3948 1288...

output:

0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 12 lines

Test #23:

score: 0
Accepted
time: 103ms
memory: 18100kb

input:

300
1000 57
801 1
1 903
29 903
1 685
685 895
685 714
1 273
666 273
930 273
273 498
677 1
677 524
618 677
677 582
677 771
1 327
330 327
327 518
844 327
259 327
364 1
422 364
43 364
364 349
364 366
373 364
1 614
614 836
718 614
459 614
657 614
335 614
614 610
614 272
523 1
118 523
523 235
523 58
523 3...

output:

0
0
0
0
0
0
0
0
0
0
0
793178976
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
21617700
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
764435931
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 300 lines

Test #24:

score: 0
Accepted
time: 144ms
memory: 24992kb

input:

100
3000 26
1 2424
1159 1
1159 2103
1159 1329
1604 1159
1159 582
160 1159
1 1484
1484 1828
1484 1911
1484 1072
1484 1457
1484 938
2036 1484
1484 2442
1484 2530
1 2471
2471 703
1464 2471
2471 1778
2471 1395
2197 2471
2471 2543
2574 2471
36 2471
1 1639
1639 1356
223 1639
281 1639
1639 817
967 1639
163...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 100 lines

Test #25:

score: 0
Accepted
time: 454ms
memory: 415600kb

input:

3
100000 141
80173 6
63209 8
22027 13
97646 17
63571 19
92352 21
87994 23
20254 24
83136 28
47623 29
69328 31
91043 32
82790 34
43140 36
60529 39
49512 41
2937 42
13921 44
8802 47
42519 48
20562 49
30829 51
21329 53
40257 58
85583 59
48601 60
75786 61
60091 62
67600 65
57659 67
6371 68
53851 73
7094...

output:

0
0
0

result:

ok 3 lines

Test #26:

score: 0
Accepted
time: 269ms
memory: 410996kb

input:

3
100000 56
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
1...

output:

0
0
0

result:

ok 3 lines

Test #27:

score: 0
Accepted
time: 369ms
memory: 427996kb

input:

3
100000 71
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 52...

output:

228906068
585530579
426277711

result:

ok 3 lines

Test #28:

score: 0
Accepted
time: 329ms
memory: 415668kb

input:

3
100000 134
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:

0
0
6502727

result:

ok 3 lines

Test #29:

score: 0
Accepted
time: 327ms
memory: 413464kb

input:

3
100000 310
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
2 31
2 32
2 33
2 34
2 35
2 36
2 37
2 38
2 39
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 47
2 48
2 49
2 50
2 51
2 52
2 53
2 54
2 55
2 56
2 57
2 58
2 59
3 60
...

output:

0
0
0

result:

ok 3 lines

Test #30:

score: 0
Accepted
time: 207ms
memory: 411724kb

input:

3
100000 23
1 2
1 3
2 4
2 5
2 6
2 7
2 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 16
4 17
4 18
4 19
4 20
4 21
4 22
4 23
4 24
5 25
5 26
5 27
5 28
5 29
5 30
5 31
5 32
5 33
5 34
5 35
6 36
6 37
6 38
6 39
6 40
6 41
6 42
6 43
6 44
6 45
6 46
6 47
6 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...

output:

0
0
0

result:

ok 3 lines

Test #31:

score: 0
Accepted
time: 387ms
memory: 414744kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #32:

score: 0
Accepted
time: 310ms
memory: 414840kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #33:

score: 0
Accepted
time: 497ms
memory: 413756kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #34:

score: 0
Accepted
time: 306ms
memory: 414944kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #35:

score: 0
Accepted
time: 275ms
memory: 419612kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #36:

score: 0
Accepted
time: 98ms
memory: 16720kb

input:

300
1000 9
520 1
638 2
625 6
21 19
670 21
258 22
118 25
825 26
729 27
533 28
665 30
71 31
116 33
158 34
468 36
927 42
137 44
558 45
942 47
427 54
561 57
16 60
15 63
931 65
585 74
40 77
576 78
873 79
311 84
601 87
225 89
846 91
633 93
350 94
593 97
531 98
334 99
666 100
979 104
809 105
386 106
184 11...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
477418661
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
988749974
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
806630583
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 300 lines

Test #37:

score: 0
Accepted
time: 83ms
memory: 15444kb

input:

300
1000 18
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
1...

output:

0
0
0
0
0
0
1000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1000
0
0
0
0
0
0
...

result:

ok 300 lines

Test #38:

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

input:

300
1000 22
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 52...

output:

323005427
941622292
7888725
960586062
878812769
960508245
878812769
30045015
710986442
381211546
77558760
901910487
901910487
19853036
636907940
941622292
636907940
583285540
319336899
467675527
253210101
989586549
7888725
987892341
30045015
636907940
583285540
30260377
960586062
901910487
901910487...

result:

ok 300 lines

Test #39:

score: 0
Accepted
time: 93ms
memory: 18100kb

input:

300
1000 14
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
2 23
3 24
4 25
5 26
6 27
7 28
8 29
9 30
10 31
11 32
12 33
13 34
14 35
15 36
16 37
17 38
18 39
19 40
20 41
21 42
22 43
23 44
24 45
25 46
26 47
27 48
28 49
29 50
30 51
31 52
32 53
33 54
34 55
3...

output:

0
419313917
0
0
0
1
0
901910487
0
0
0
105457563
0
0
0
895993044
1
960586062
691020710
0
834938939
464387622
912996466
0
0
122100405
0
0
0
0
208596912
0
640434527
43348745
0
897296141
941622292
10518300
0
362363366
261311097
0
0
422253306
0
0
0
0
323497662
0
0
0
0
737109138
600008834
0
257542067
0
0
...

result:

ok 300 lines

Test #40:

score: 0
Accepted
time: 89ms
memory: 18040kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
385259412
0
0
392114570
0
0
0
435253942
901501642
0
0
0
0
0
0
0
0
0
0
12155170
0
0
0
0
0
228488
0
0
0
0
0
0
0
0
0
0
901501642
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 300 lines

Test #41:

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

input:

300
1000 16
1 2
1 3
2 4
2 5
2 6
2 7
2 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 16
4 17
4 18
4 19
4 20
4 21
4 22
4 23
4 24
5 25
5 26
5 27
5 28
5 29
5 30
5 31
5 32
5 33
5 34
5 35
6 36
6 37
6 38
6 39
6 40
6 41
6 42
6 43
6 44
6 45
6 46
6 47
6 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...

output:

0
0
0
0
0
0
0
0
0
0
333550771
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
333550771
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
333550771
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
333550771
0
0
0
0
0
0
0
0
0
0
33355077...

result:

ok 300 lines

Test #42:

score: 0
Accepted
time: 97ms
memory: 16784kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
778308991
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
43200629
0
0
0
0
0
0
0
0...

result:

ok 300 lines

Test #43:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
694166651
196634955
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
543130652
0
0
0
0
0
0
0
129188971
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
582516300
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 300 lines

Test #44:

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

input:

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

output:

0
133749621
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
244103312
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
183143151
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 300 lines

Test #45:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
274762166
0
0
0
0
0
0
0
0
0
0
0
0
0
398132450
0
0
587717342
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
587717342
0
398132450
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
587717342
0
274762166
0
0
0
0
0
0
0
0
398132450
0
0
...

result:

ok 300 lines

Test #46:

score: 0
Accepted
time: 90ms
memory: 17148kb

input:

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

output:

0
0
0
0
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
556586257
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
556586257
0
0
0
0
0
...

result:

ok 300 lines

Test #47:

score: 0
Accepted
time: 422ms
memory: 415040kb

input:

3
100000 157
62020 6
19963 7
7238 10
37922 14
79431 15
83118 16
66558 18
16837 22
68998 26
17764 36
67025 43
33934 55
91228 58
40295 62
43491 63
80707 64
73846 68
5817 69
95212 70
73148 71
93720 77
59916 81
85914 82
81320 83
3384 85
60680 87
89965 89
60201 90
66529 92
41320 93
69082 94
93875 96
5329...

output:

0
0
0

result:

ok 3 lines

Test #48:

score: 0
Accepted
time: 357ms
memory: 415220kb

input:

3
100000 226
29677 3
43410 4
79556 5
35809 6
3528 7
76465 8
63634 16
59070 21
35525 29
3739 30
39762 34
28625 36
82910 40
94087 41
41506 46
8963 50
44915 57
50544 58
29442 61
31296 62
3844 63
60917 67
76565 71
11451 73
75481 74
44793 76
90148 77
91625 78
76219 79
65699 83
92442 84
80289 88
48280 89
...

output:

0
0
0

result:

ok 3 lines

Test #49:

score: 0
Accepted
time: 451ms
memory: 414968kb

input:

3
100000 172
13124 2
30283 3
21907 8
20768 9
42188 14
72816 19
54692 26
86076 28
85259 30
79153 36
33409 37
40734 38
23240 42
7686 43
44026 44
34936 45
21565 47
14428 52
56244 53
87759 59
15673 60
8242 63
36808 65
36958 68
21086 69
32987 73
31459 74
18609 76
68964 77
38494 78
49125 83
79818 86
85237...

output:

0
0
0

result:

ok 3 lines

Test #50:

score: 0
Accepted
time: 418ms
memory: 415712kb

input:

3
100000 327
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
2 24
3 25
4 26
5 27
6 28
7 29
8 30
9 31
10 32
11 33
12 34
13 35
14 36
15 37
16 38
17 39
18 40
19 41
20 42
21 43
22 44
23 45
24 46
25 47
26 48
27 49
28 50
29 51
30 52
31 53
32 54
33 55
3...

output:

0
0
647948500

result:

ok 3 lines

Test #51:

score: 0
Accepted
time: 430ms
memory: 415060kb

input:

3
100000 158
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:

0
0
0

result:

ok 3 lines

Test #52:

score: 0
Accepted
time: 344ms
memory: 415212kb

input:

3
100000 234
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:

0
0
179356563

result:

ok 3 lines

Test #53:

score: 0
Accepted
time: 301ms
memory: 414328kb

input:

3
100000 179
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:

0
0
0

result:

ok 3 lines

Test #54:

score: 0
Accepted
time: 317ms
memory: 413044kb

input:

3
100000 151
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:

0
0
0

result:

ok 3 lines

Test #55:

score: 0
Accepted
time: 369ms
memory: 413056kb

input:

3
100000 333
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:

0
0
0

result:

ok 3 lines

Test #56:

score: 0
Accepted
time: 401ms
memory: 411772kb

input:

3
100000 288
1 2
1 3
2 4
2 5
2 6
2 7
2 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 16
4 17
4 18
4 19
4 20
4 21
4 22
4 23
4 24
5 25
5 26
5 27
5 28
5 29
5 30
5 31
5 32
5 33
5 34
5 35
6 36
6 37
6 38
6 39
6 40
6 41
6 42
6 43
6 44
6 45
6 46
6 47
6 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
...

output:

0
0
0

result:

ok 3 lines

Test #57:

score: 0
Accepted
time: 398ms
memory: 411064kb

input:

3
100000 226
1 2
1 3
2 4
2 5
2 6
2 7
2 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 16
4 17
4 18
4 19
4 20
4 21
4 22
4 23
4 24
5 25
5 26
5 27
5 28
5 29
5 30
5 31
5 32
5 33
5 34
5 35
6 36
6 37
6 38
6 39
6 40
6 41
6 42
6 43
6 44
6 45
6 46
6 47
6 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
...

output:

0
0
0

result:

ok 3 lines

Test #58:

score: 0
Accepted
time: 414ms
memory: 412280kb

input:

3
100000 170
1 2
1 3
2 4
2 5
2 6
2 7
2 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 16
4 17
4 18
4 19
4 20
4 21
4 22
4 23
4 24
5 25
5 26
5 27
5 28
5 29
5 30
5 31
5 32
5 33
5 34
5 35
6 36
6 37
6 38
6 39
6 40
6 41
6 42
6 43
6 44
6 45
6 46
6 47
6 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
...

output:

0
0
0

result:

ok 3 lines

Test #59:

score: 0
Accepted
time: 469ms
memory: 414920kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #60:

score: 0
Accepted
time: 398ms
memory: 414908kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #61:

score: 0
Accepted
time: 384ms
memory: 414928kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #62:

score: 0
Accepted
time: 291ms
memory: 413924kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #63:

score: 0
Accepted
time: 280ms
memory: 413672kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #64:

score: 0
Accepted
time: 466ms
memory: 413724kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #65:

score: 0
Accepted
time: 311ms
memory: 414948kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #66:

score: 0
Accepted
time: 335ms
memory: 414948kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #67:

score: 0
Accepted
time: 343ms
memory: 415012kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #68:

score: 0
Accepted
time: 327ms
memory: 419536kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #69:

score: 0
Accepted
time: 354ms
memory: 419840kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #70:

score: 0
Accepted
time: 224ms
memory: 419984kb

input:

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

output:

0
0
0

result:

ok 3 lines

Test #71:

score: 0
Accepted
time: 336ms
memory: 414972kb

input:

3
100000 69
79560 4
57278 5
54319 8
14086 10
99883 13
41319 14
21256 17
84702 18
75114 22
62679 26
40625 27
47767 28
2526 30
59325 34
310 36
12483 37
86853 38
72521 40
85701 42
70709 45
15200 46
34100 48
59219 49
5349 51
89300 54
12534 59
79157 60
61807 62
71433 63
28302 68
80583 70
2803 74
52206 75...

output:

0
0
0

result:

ok 3 lines

Test #72:

score: 0
Accepted
time: 203ms
memory: 411760kb

input:

3
100000 7
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
1 ...

output:

0
0
0

result:

ok 3 lines

Extra Test:

score: 0
Extra Test Passed