QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310436#7181. Graph CutsZhangYiDeTL 519ms101516kbC++142.4kb2024-01-21 14:11:032024-01-21 14:11:03

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8756kb

input:

4 5
1 2
1 3
1 4
2 3
2 4
10
+ 1
+ 2
?
?
?
?
?
- 2
?
?

output:

2
4
3
5
0
1
0

result:

ok q=10

Test #2:

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

input:

0 0
0

output:


result:

ok q=0

Test #3:

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

input:

0 0
1
?

output:

0

result:

ok q=1

Test #4:

score: 0
Accepted
time: 519ms
memory: 9348kb

input:

1000 2000
1 50
1 88
331 1
1 352
1 497
2 32
2 282
550 2
989 2
334 3
3 665
4 38
4 69
4 343
4 451
589 4
917 4
89 5
5 162
675 5
681 6
7 22
127 7
7 592
7 672
787 7
8 310
107 9
9 137
184 9
9 244
378 9
446 9
9 658
883 9
65 10
75 10
414 10
10 468
686 10
245 11
269 11
11 386
403 11
493 11
394 12
493 12
565 1...

output:

1476
1289
1403
900
1462
1463
1464
533
1591
1003
1145
1324
1132
1482
1481
1610
755
1609
1182
748
1608
1663
1662
1661
911
1547
1696
210
211
214
213
1046
1048
1238
727
1369
233
814
56
1928
108
109
439
1838
442
768
770
157
766
767
885
648
251
565
893
1170
1695
667
1279
1537
1694
1548
778
1836
896
548
67...

result:

ok q=100000

Test #5:

score: 0
Accepted
time: 312ms
memory: 101412kb

input:

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

output:

3094

result:

ok q=100000

Test #6:

score: 0
Accepted
time: 350ms
memory: 75224kb

input:

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

output:

81623
94359
29078
94409
94415
18977
89138
94332
59108
43298
44300
69932
94425
62177
88253
40925
35675
94394
75268
61903
34598
94419
94382
94337
87332
94418
18575
9478
94365
63263
2558
84002
73243
17363
20177
94402
19778
66167
94428
46277
94355
94364
32417
75925
38503
55918
48538
94373
17768
72317
89...

result:

ok q=100000

Test #7:

score: 0
Accepted
time: 381ms
memory: 52216kb

input:

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

output:

64186
36596
11021
42140
65761
641
56945
68330
68415
40091
68490
60928
55771
68528
68403
68465
68417
68549
68331
25511
68491
23965
68334
5903
68377
31903
29306
68391
65501
22795
68553
56066
68428
37303
29680
68414
68486
68502
66278
67553
10178
62846
68478
68381
17216
52460
68543
68450
47750
68433
684...

result:

ok q=100000

Test #8:

score: 0
Accepted
time: 395ms
memory: 35068kb

input:

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

output:

0
34271
53252
48891
37484
97306
78497
56541
78702
43667
87831
12041
97330
73506
46637
97268
63566
97127
74187
67227
92942
97303
66716
77457
56247
9087
90296
88136
66459
83141
70209
97317
89459
96686
87522
39581
13292
14121
61386
45984
69966
95334
82221
90701
12876
97285
89316
97267
33981
94256
35115...

result:

ok q=100000

Test #9:

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

input:

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

output:

0
0
0
0
0
0
0
0
94763
40586
33152
94958
40588
94748
94762
33154
94943
94957
50473
67197
52304
65391
67199
52306
91956
87179
65393
94777
91958
87181
86052
94972
86054
40371
94800
38157
94995
38159
32937
50458
50472
50285
94755
77846
94821
94950
77848
95016
50232
94788
60522
90129
50127
40242
89142
18...

result:

ok q=100000

Test #10:

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

input:

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

output:

0
0
0
0
51203
62330
62467
62484
62389
62480
55452
41438
51469
74921
96019
97328
86308
97046
20367
20455
51219
66562
20592
66699
20609
66716
23904
23992
24129
24146
20514
66621
24051
20605
66712
24142
55718
20381
55468
51304
74756
84889
84906
84811
84902
23918
55553
41704
20337
41454
23874
41539
4995...

result:

ok q=100000

Test #11:

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

input:

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

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #12:

score: 0
Accepted
time: 281ms
memory: 101516kb

input:

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

output:

29386

result:

ok q=100000

Test #13:

score: 0
Accepted
time: 373ms
memory: 74732kb

input:

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

output:

2578
4332
4768
5203
5637
6933
7363
7792
9073
9498
10345
11188
96260
36052
69952
94033
24132
17383
70195
96257
15753
96238
53238
22962
84373
93382
84022
66702
64353
48238
10767
45642
94747
96202
58270
67972
96245
96198
83488
12027
13693
14520
15343
16570
18192
18595
21388
22570
24520
24907
26445
2682...

result:

ok q=100000

Test #14:

score: 0
Accepted
time: 375ms
memory: 52468kb

input:

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

output:

44
489
933
1376
1818
2699
3138
3576
4013
4884
5751
6614
7044
7901
8328
9179
9603
10448
10869
11289
12126
12543
14201
14613
15024
15843
18276
18680
18684
18685
18687
18688
18689
18690
18691
18693
18694
18695
18698
18699
18702
18703
18706
18707
18708
18709
18711
18712
18713
18717
18718
18723
18724
187...

result:

ok q=100000

Test #15:

score: 0
Accepted
time: 388ms
memory: 34756kb

input:

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

output:

14474
14326
14381
14315
14219
14551
14217
14289
14260
14492
14491
14500
14242
14251
14241
14371
14322
14497
14437
10015
14559
14238
14464
14385
14267
8743
14573
14237
14394
14590
14297
14196
14462
14490
14538
14306
14423
14459
14357
14193
14380
14587
14468
14279
14384
14584
14247
14298
14507
14366
1...

result:

ok q=100000

Test #16:

score: 0
Accepted
time: 304ms
memory: 22052kb

input:

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

output:

799
1686
3009
3448
5194
5628
6924
7354
8638
9064
10336
10758
11599
12018
12853
13269
13684
14098
14511
14923
15744
16561
16968
17779
18183
18586
19389
19789
20188
20983
21774
22561
24123
25284
25669
26053
26436
28336
28713
29089
31324
32061
32794
33159
33523
33886
34248
35328
35686
36043
37813
39558...

result:

ok q=100000

Test #17:

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

input:

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

output:

4785
4666
4604
4724
4422
4725
4465
4599
4706
4588
4497
4514
4621
4806
4630
4473
4749
4716
4812
4451
4672
4513
4603
4488
4774
4536
4693
4820
4644
4656
4626
4809
4468
4707
4561
4709
4833
4755
4531
4475
4650
4595
4654
4602
4456
4637
4568
4664
4822
4826
4847
4653
4435
4843
4580
4738
4615
4825
4745
4717
...

result:

ok q=100000

Test #18:

score: 0
Accepted
time: 82ms
memory: 10968kb

input:

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

output:

2829
2703
2777
2867
2719
3024
3093
2784
2950
2796
3045
2863
3053
2803
2807
2924
3031
2958
2882
2843
2873
3071
2894
2817
3080
3038
2955
2942
2920
2789
3003
2675
2815
2822
2999
2797
2792
2748
2850
3027
2752
2871
3012
2832
2768
2880
2951
2764
2697
3017
2841
2713
3006
3065
2970
2761
3086
2978
2956
2967
...

result:

ok q=100000

Test #19:

score: 0
Accepted
time: 282ms
memory: 101460kb

input:

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

output:

468

result:

ok q=100000

Test #20:

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

input:

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

output:

7307
10711
14876
16514
18941
26006
29417
31277
33476
33839
34562
34922
37061
41231
41572
42589
46567
47539
48182
48502
48821
50087
51647
53789
54692
56177
56471
60202
62141
62686
63227
64297
64826
65351
65872
66389
68417
68914
72281
73207
73664
73891
76322
76964
77387
77806
78221
79442
81014
81397
8...

result:

ok q=100000

Test #21:

score: 0
Accepted
time: 404ms
memory: 52456kb

input:

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

output:

873
22242
25743
42710
97893
21848
75132
93558
81518
75573
98232
93885
9138
97518
76443
88187
84438
94613
84785
51147
97772
81708
87102
47337
93335
428
83010
92523
87573
60042
89367
34683
39632
84087
96177
58622
99515
99524
89652
21057
9563
61437
53910
74687
17042
97952
34322
89078
95292
27273
99513
...

result:

ok q=100000

Test #22:

score: 0
Accepted
time: 380ms
memory: 34464kb

input:

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

output:

0
0
60453
60600
32971
60396
60551
53950
60550
15146
60416
59780
11830
60535
60369
60526
60395
60576
60480
60414
60593
60439
45773
60615
60520
27391
60478
60483
52736
85517
90480
60421
60403
37273
60583
60496
60366
60444
60484
37625
60541
60554
60410
60565
60349
2821
60610
48680
60511
60592
60585
358...

result:

ok q=100000

Test #23:

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

input:

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

output:

81179
85889
65845
65767
69843
69938
24049
42562
85836
23971
54964
50060
47189
42484
80987
69885
54886
49982
19315
47111
16487
69842
19237
16409
6419
6341
6190
16258
19086
21477
85845
69894
21528
21542
21551
21567
21606
18109
85867
85835
18031
85832
72719
69916
69884
69881
38440
69134
69803
63469
228...

result:

ok q=100000

Test #24:

score: 0
Accepted
time: 181ms
memory: 13680kb

input:

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

output:

0
0
0
0
34597
21367
59674
83287
14086
69196
34417
21187
59212
59314
34457
21227
59534
69854
13906
13946
59248
69056
76357
59279
69819
81432
59304
34425
21195
34678
34573
21448
34407
21343
21177
9220
34389
34641
9185
21159
21411
34357
34581
21127
34563
34406
21351
21333
28444
34651
21176
21094
21421
...

result:

ok q=100000

Test #25:

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

input:

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

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #26:

score: 0
Accepted
time: 345ms
memory: 101364kb

input:

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

output:

511

result:

ok q=100000

Test #27:

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

input:

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

output:

43455
43262
43364
43227
31858
43173
43384
22735
43453
11789
5390
12624
43328
43459
39021
43391
29630
43281
43202
43132
43185
37971
43253
43201
43312
43302
32592
1884
43188
17150
43257
43240
43216
43381
43452
43283
43294
43220
43293
43206
43347
43182
15109
43421
43254
43267
43320
43304
43345
43160
40...

result:

ok q=100000

Test #28:

score: 0
Accepted
time: 413ms
memory: 52452kb

input:

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

output:

33747
61643
2829
61683
4146
61670
49385
16401
61589
61684
61685
61716
61677
61708
50646
56708
61666
61626
61668
5453
61654
22800
22407
61590
58162
61662
61557
61796
61658
36617
61549
61736
61552
3708
51270
61739
61762
54631
61628
43852
61806
61599
41830
61585
61612
61723
35907
1060
61780
54931
61550...

result:

ok q=100000

Test #29:

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

input:

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

output:

19035
39984
19065
40014
55736
18973
18940
933
18786
18730
18876
18855
19093
18864
18817
18714
18851
19094
19080
18881
19084
12132
18812
18861
11713
19097
18808
19004
18931
18843
18722
19092
18992
19091
18980
19016
9605
18731
18773
18985
19010
18845
18944
19024
18732
18709
17889
19042
18885
18717
189...

result:

ok q=100000

Test #30:

score: 0
Accepted
time: 307ms
memory: 21864kb

input:

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

output:

0
6392
79742
79821
79818
79840
6399
81115
81195
6474
83063
6281
51046
6359
72588
92885
51126
72668
6554
6265
83143
6494
6224
45926
6225
6308
83083
31268
31638
6354
59109
71171
6515
6338
83104
67215
94614
46006
6545
83134
6266
6229
46254
6510
33108
6564
6252
6277
6574
6570
83099
83153
49790
83163
627...

result:

ok q=100000

Test #31:

score: 0
Accepted
time: 181ms
memory: 13908kb

input:

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

output:

0
0
0
0
0
0
48471
48584
66913
67027
70158
70272
61311
61425
48568
67011
70256
61409
21172
21235
48678
48505
48486
67122
66947
66928
48490
66932
21248
70367
70192
70173
70177
21214
61520
61345
61326
61330
65094
65208
65192
21228
26231
5406
48433
16762
48679
26295
5470
64273
16826
67123
26308
5483
642...

result:

ok q=100000

Test #32:

score: 0
Accepted
time: 63ms
memory: 10312kb

input:

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

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #33:

score: 0
Accepted
time: 333ms
memory: 101448kb

input:

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

output:

2653

result:

ok q=100000

Test #34:

score: 0
Accepted
time: 388ms
memory: 75444kb

input:

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

output:

312
84480
81549
67769
53559
14896
90988
88248
77944
65187
79383
21360
83592
90695
90983
91001
24108
17756
87941
90992
68274
69765
70254
69272
31683
91076
78774
90285
46629
44654
90969
91079
90997
79985
91021
91017
17350
91097
66748
78979
57722
9878
72869
91085
18968
1201
1645
2088
2530
2969
3408
384...

result:

ok q=100000

Test #35:

score: 0
Accepted
time: 409ms
memory: 53000kb

input:

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

output:

73458
73413
73435
12730
73445
35232
23235
73350
73410
5495
73387
73306
73329
73354
4193
65094
73429
73362
27474
73404
50377
50063
73265
73283
22056
73392
60758
71356
73363
73384
73312
61036
4628
67418
73461
73319
57045
73334
73254
73433
70395
73457
73278
15215
18065
69418
33425
49748
73343
14390
733...

result:

ok q=100000

Test #36:

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

input:

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

output:

34004
78894
43778
96066
86467
19079
97276
48049
93545
95327
98085
99638
57838
24611
99644
38640
97349
28066
61248
52150
31807
72048
84600
864
81282
88820
62079
95704
17462
63172
99194
94934
48690
80304
95423
41408
68395
4395
17868
67637
99379
70127
97631
63710
91988
23833
91476
80502
98700
57547
545...

result:

ok q=100000

Test #37:

score: 0
Accepted
time: 315ms
memory: 22124kb

input:

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

output:

64180
22019
64210
55537
64243
64134
49714
30448
41162
64197
43532
64055
18026
35560
64144
53737
64089
64263
23197
64245
64176
29326
64178
64220
64060
64161
11014
13107
50970
64066
5024
43197
35201
25527
64071
17216
58460
64213
46832
62379
64192
49080
625
64256
64207
16809
64092
64164
64088
64046
641...

result:

ok q=100000

Test #38:

score: 0
Accepted
time: 183ms
memory: 13924kb

input:

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

output:

64184
97163
85065
10357
8660
88912
35026
2589
37874
66808
96443
6946
81418
30630
45377
76731
53313
8234
86413
24947
97222
63648
58066
26486
34304
47339
97216
36102
90619
49267
11622
19024
3905
81610
93032
67828
41684
20227
97158
91934
81031
92795
84719
65246
95466
97162
97211
96689
40656
62290
94368...

result:

ok q=100000

Test #39:

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

input:

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

output:

829
584
847
609
573
777
604
612
767
689
866
860
716
840
852
823
663
757
530
815
613
811
509
701
714
735
873
892
769
629
540
808
794
547
666
548
516
514
858
717
485
684
721
579
655
830
662
627
618
590
478
883
664
725
820
605
459
522
677
790
469
868
597
711
603
599
490
732
761
1
452
488
801
600
568
83...

result:

ok q=100000

Test #40:

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

input:

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

output:

918

result:

ok q=100000

Test #41:

score: 0
Accepted
time: 371ms
memory: 75320kb

input:

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

output:

33893
44340
45665
53579
54185
56276
58892
67025
71945
76033
76682
77955
79193
85015
87330
87644
89447
89876
90571
90707
90975
91108
91240
91371
92510
92511
92513
92518
92520
92523
92524
92528
92529
92531
92532
92534
92538
92544
92549
92551
92553
92554
92558
92571
92574
92575
92579
92583
92587
92590
...

result:

ok q=100000

Test #42:

score: 0
Accepted
time: 399ms
memory: 52476kb

input:

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

output:

0
58432
39408
13911
58370
23166
58149
58333
8451
58154
58193
42492
58323
58429
58305
58235
24723
58310
58344
58322
58302
58195
58245
2819
28922
58281
58177
58273
33363
40446
58287
58361
45167
58319
58434
58346
45824
58337
58373
50005
58324
44505
58252
58394
58226
10990
58380
58277
11829
58317
58163
...

result:

ok q=100000

Test #43:

score: 0
Accepted
time: 402ms
memory: 35064kb

input:

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

output:

0
0
0
0
0
0
0
18028
28944
65117
18218
29135
18195
18159
29112
18119
18084
18103
6188
29075
17983
29035
29000
29019
6216
17946
17929
18172
18275
18240
28900
17947
28863
18153
18216
932
18029
18221
18187
18270
18283
17932
18177
28846
29089
18014
17993
29192
18042
28864
29069
18198
17896
960
18242
2894...

result:

ok q=100000

Test #44:

score: 0
Accepted
time: 303ms
memory: 22040kb

input:

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

output:

42908
42909
15510
43066
77477
45570
41209
77458
77688
45571
41210
77669
15659
15518
15506
15640
58228
44579
65377
44580
61060
77544
4646
65378
61061
77755
4647
63786
77646
75068
77564
36323
77600
66160
47204
77666
74397
77570
66934
63787
77575
77857
75069
47849
77608
77581
8952
77561
77775
681
77466...

result:

ok q=100000

Test #45:

score: 0
Accepted
time: 193ms
memory: 13896kb

input:

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

output:

0
12739
35597
61317
75096
12888
35746
61465
84711
51009
51158
75085
82734
75219
97247
44571
12655
35513
12611
12712
12689
35469
12936
35570
35547
35794
52810
38375
61290
61267
61513
52913
38478
12943
35801
61520
68734
62737
84759
84766
12796
35654
61374
84619
50925
38340
50982
50959
51205
51212
5106...

result:

ok q=100000

Test #46:

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

input:

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

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #47:

score: -100
Time Limit Exceeded

input:

100000 100000
5722 1
35633 1
76503 1
2 8454
2 93428
3 91414
4 55025
21132 5
6 22400
6 80941
7 22043
7 29361
7 73158
78568 7
8 24159
8 26175
27612 9
39375 9
5454 10
24262 10
40601 10
11 8620
59525 11
11 79781
11 92891
64034 12
33728 14
14 59378
14 79826
560 16
16 31445
35262 16
17911 17
28509 17
9364...

output:


result: