QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713679#7181. Graph CutsZhaoZiLongML 107ms16464kbC++20980b2024-11-05 20:16:072024-11-05 20:16:08

详细

Test #1:

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

input:

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

output:

2
3
4
5
0
1
0

result:

ok q=10

Test #2:

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

input:

0 0
0

output:


result:

ok q=0

Test #3:

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

input:

0 0
1
?

output:

0

result:

ok q=1

Test #4:

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

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:

1
4
5
8
9
10
12
14
16
18
19
25
27
29
33
38
39
40
42
47
48
49
50
56
58
59
62
63
67
69
70
71
73
75
79
81
82
83
84
87
89
91
94
97
101
103
104
106
107
108
109
110
113
114
115
118
120
121
122
125
126
129
130
131
132
133
134
135
137
145
147
148
34
149
152
153
154
155
156
157
159
160
163
167
171
105
173
17...

result:

ok q=100000

Test #5:

score: 0
Accepted
time: 106ms
memory: 9968kb

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:

6

result:

ok q=100000

Test #6:

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

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:

70
44
110
103
88
113
85
161
171
172
21
43
5
176
40
46
47
41
18
53
3
55
11
37
69
79
82
2
94
1
4
6
7
8
9
10
12
13
14
15
16
17
19
20
24
25
26
27
28
29
30
31
32
33
34
35
36
38
45
48
49
51
52
54
57
58
59
60
61
62
63
64
65
66
67
68
71
72
73
75
77
78
81
83
86
90
91
42
92
93
95
96
102
76
105
106
109
111
118...

result:

ok q=100000

Test #7:

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

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:

180
25
1
91
101
107
137
13
54
57
61
71
72
78
23
40
93
37
103
124
126
138
139
145
150
151
154
160
168
8
175
102
68
158
34
77
94
118
185
159
186
106
128
26
162
172
62
90
21
184
7
20
120
188
82
92
112
33
59
130
144
152
173
174
181
189
191
161
192
193
196
205
211
45
89
142
35
153
127
163
166
212
221
222...

result:

ok q=100000

Test #8:

score: 0
Accepted
time: 75ms
memory: 10824kb

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
84
93
27
111
120
127
141
20
151
152
177
189
191
217
220
235
240
241
292
188
264
294
309
203
290
303
330
369
30
32
99
375
379
118
169
202
259
312
320
353
414
417
29
302
378
396
428
441
342
465
156
286
472
47
155
1
2
3
4
5
6
7
8
9
10
12
13
14
15
16
17
18
19
21
22
23
24
25
26
28
31
33
34
35
36
37
38
...

result:

ok q=100000

Test #9:

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

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
81
102
379
526
547
364
378
809
823
824
970
138
184
191
583
629
288
322
636
393
733
767
281
726
838
991
416
95
540
861
984
1027
1073
1080
371
237
437
682
816
882
1126
166
308
43
101
131
211
111
301
339
404
488
546
310
255
556
576
611
656
90
436
535
267
700
258
703
712
746
753
319
755
...

result:

ok q=100000

Test #10:

score: 0
Accepted
time: 72ms
memory: 9268kb

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
173
618
1062
1505
1947
2388
2828
3267
439
884
1328
1771
2213
2654
48
493
189
634
937
1078
1380
1521
57
502
946
1389
1822
1831
1963
2263
2272
2404
2703
2712
2844
274
719
1163
1606
2048
2489
2929
3094
3142
3151
3283
3368
3533
3580
3589
3705
3721
3806
3971
4017
4026
4142
261
706
376
821
121
202...

result:

ok q=100000

Test #11:

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

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: 101ms
memory: 10188kb

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:

2

result:

ok q=100000

Test #13:

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

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:

5
9
10
11
12
15
16
17
20
21
23
25
31
33
35
42
43
50
52
53
58
1
2
3
4
6
7
8
13
14
18
19
22
24
26
29
30
32
34
28
36
37
39
40
41
44
45
46
47
48
49
51
54
55
56
57
60
61
62
64
65
66
68
63
27
70
71
72
74
75
81
84
86
90
93
95
92
96
98
100
101
102
103
104
109
112
114
118
120
122
123
125
129
110
132
135
137
...

result:

ok q=100000

Test #14:

score: 0
Accepted
time: 80ms
memory: 9996kb

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:

5
10
11
12
14
17
20
23
27
30
31
32
36
38
39
40
41
42
44
45
47
48
22
49
52
58
60
62
63
29
66
67
43
16
50
70
71
76
80
81
82
25
85
86
87
88
92
94
95
98
100
102
103
106
107
108
109
110
113
114
115
116
96
119
120
123
84
128
129
130
133
134
137
140
144
145
150
151
152
153
154
158
162
163
164
138
165
169
1...

result:

ok q=100000

Test #15:

score: 0
Accepted
time: 74ms
memory: 10380kb

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:

2
3
4
6
7
8
10
11
12
13
14
15
16
17
18
20
21
22
23
25
27
28
31
34
35
36
38
39
42
43
44
46
48
52
58
59
60
61
62
65
66
68
72
75
80
81
82
84
85
90
91
40
50
73
93
94
95
86
97
98
100
102
103
104
105
106
110
113
115
117
118
119
122
125
132
134
53
135
26
136
138
140
141
142
145
146
147
149
150
151
1
154
15...

result:

ok q=100000

Test #16:

score: 0
Accepted
time: 70ms
memory: 10820kb

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:

1
3
6
7
11
12
15
16
19
20
23
24
26
27
29
30
31
32
33
34
36
38
39
41
42
43
45
46
47
49
51
53
57
60
61
62
63
68
69
13
70
76
78
80
81
82
83
84
87
88
89
94
99
101
103
104
109
114
115
116
119
120
124
126
127
128
130
131
134
136
138
139
140
141
143
144
145
148
151
152
153
154
155
156
157
158
160
161
164
1...

result:

ok q=100000

Test #17:

score: 0
Accepted
time: 72ms
memory: 10800kb

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:

1
2
3
5
6
7
8
9
10
11
14
16
19
20
22
23
24
26
28
34
36
37
38
39
41
42
48
50
52
56
57
58
61
64
65
66
69
72
73
74
75
77
80
84
85
86
88
91
93
96
98
100
101
103
104
112
113
114
116
117
120
122
124
130
133
136
138
141
142
143
145
146
148
149
154
155
160
162
165
167
170
171
172
174
176
177
180
182
184
189...

result:

ok q=100000

Test #18:

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

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:

6
7
8
9
10
11
13
14
16
17
19
21
22
23
24
25
28
30
31
36
37
38
39
40
41
43
45
49
52
53
55
57
60
61
66
67
68
69
70
71
72
74
75
77
78
79
81
82
83
84
88
90
91
96
98
100
104
105
107
108
110
111
112
115
116
118
119
120
121
123
127
130
131
135
140
143
144
150
151
156
159
161
163
165
168
169
171
173
179
180...

result:

ok q=100000

Test #19:

score: 0
Accepted
time: 101ms
memory: 10288kb

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:

1

result:

ok q=100000

Test #20:

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

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:

16
24
34
38
1
43
44
32
57
61
62
69
71
76
64
39
66
10
68
72
22
18
40
46
49
55
82
83
85
86
6
41
51
12
20
81
92
26
52
4
21
28
56
59
84
102
104
105
108
109
120
123
125
126
107
127
8
131
47
75
132
42
134
5
53
136
137
3
111
13
135
35
31
54
95
99
50
133
138
139
17
141
143
144
149
150
48
25
30
63
77
152
154...

result:

ok q=100000

Test #21:

score: 0
Accepted
time: 79ms
memory: 10204kb

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:

1
52
61
108
83
69
182
33
200
240
208
236
57
77
102
10
90
110
126
127
43
142
160
13
21
30
155
193
196
206
158
214
37
59
119
194
48
62
186
201
18
22
116
141
179
176
107
20
28
118
143
93
138
148
180
192
215
24
132
85
217
172
227
231
232
147
233
234
128
235
146
242
243
27
246
254
255
256
99
223
257
260
...

result:

ok q=100000

Test #22:

score: 0
Accepted
time: 76ms
memory: 10296kb

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
81
144
221
35
278
375
241
164
27
194
220
239
305
264
118
66
303
308
345
351
360
376
401
418
425
440
140
472
480
246
93
94
191
228
6
174
235
269
127
309
321
89
336
366
72
162
311
358
199
274
361
379
7
65
390
42
102
124
399
408
410
417
435
451
22
452
48
320
161
198
37
215
222
120
223
70
69
209
9
2...

result:

ok q=100000

Test #23:

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

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:

254
186
349
631
699
794
57
108
296
502
131
122
147
553
253
567
576
592
45
490
38
483
698
741
14
459
903
927
934
946
305
750
997
1011
1020
1036
1075
42
295
327
487
214
292
659
737
740
96
199
541
54
177
420
499
622
644
285
168
364
143
380
416
588
613
730
772
809
370
401
815
825
846
861
865
931
943
153...

result:

ok q=100000

Test #24:

score: 0
Accepted
time: 67ms
memory: 9020kb

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
342
787
1231
1674
2116
2557
162
607
1051
1494
202
647
1091
1534
1936
1976
2377
2417
2817
2857
2997
3256
3296
170
615
423
318
763
152
597
868
21
134
386
466
579
831
102
326
547
308
151
596
753
69
396
514
771
841
186
631
15
460
360
805
904
395
840
910
958
87
106
111
532
551
556
443
888
976
991...

result:

ok q=100000

Test #25:

score: 0
Accepted
time: 81ms
memory: 10444kb

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: 106ms
memory: 10904kb

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:

1

result:

ok q=100000

Test #27:

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

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:

242
78
207
4
12
27
29
35
40
54
14
22
23
19
49
11
72
3
77
80
17
28
26
1
10
30
43
15
25
21
48
52
59
66
84
94
65
95
98
99
101
85
108
24
56
50
70
42
44
46
75
105
109
111
112
120
123
55
124
129
104
130
82
91
6
131
7
51
83
96
100
113
121
13
88
117
128
61
79
132
87
127
133
76
41
81
89
134
110
137
140
86
14...

result:

ok q=100000

Test #28:

score: 0
Accepted
time: 85ms
memory: 9620kb

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:

6
9
83
38
129
264
210
291
304
305
306
337
133
12
8
53
54
91
112
106
135
2
89
13
136
146
147
3
17
149
153
158
21
58
105
116
85
110
130
164
171
172
102
142
43
174
179
206
211
216
220
104
117
199
100
230
90
193
233
42
123
27
131
219
84
152
124
34
81
96
1
4
5
7
10
11
14
15
16
18
20
22
23
24
25
26
28
29
...

result:

ok q=100000

Test #29:

score: 0
Accepted
time: 72ms
memory: 9560kb

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:

383
829
413
859
1274
2
288
64
80
136
166
200
204
212
224
27
28
157
161
209
72
192
22
81
123
229
279
321
328
194
333
340
352
292
358
59
82
364
42
372
390
428
432
439
440
441
442
67
233
445
218
55
141
283
32
63
196
327
354
425
446
466
471
163
261
263
400
430
472
370
165
476
499
503
507
508
511
516
58
...

result:

ok q=100000

Test #30:

score: 0
Accepted
time: 74ms
memory: 10168kb

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
246
692
1137
1581
2023
253
699
1144
328
774
134
580
213
659
1025
1104
1219
408
118
564
348
76
522
77
161
523
607
794
207
653
854
191
369
637
815
967
968
399
845
119
81
527
364
565
104
130
418
424
428
550
576
810
864
126
10
215
239
456
79
154
423
286
31
133
477
525
572
579
600
270
661
685
716
732
8...

result:

ok q=100000

Test #31:

score: 0
Accepted
time: 68ms
memory: 9484kb

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
218
332
663
777
1108
1222
1552
1666
316
761
1206
1650
50
495
252
233
426
678
697
872
237
682
940
1123
1127
1142
1317
1384
1567
1571
1586
1761
1827
1995
2010
2014
12
39
63
180
427
457
484
508
625
873
902
929
953
1070
1318
1346
1373
1397
238
683
73
518
963
1128
1407
1514
1572
1762
1789
181...

result:

ok q=100000

Test #32:

score: 0
Accepted
time: 80ms
memory: 10508kb

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: 106ms
memory: 10988kb

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:

5

result:

ok q=100000

Test #34:

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

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:

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

result:

ok q=100000

Test #35:

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

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:

4
7
14
15
18
20
22
24
25
26
27
31
34
36
5
37
38
39
40
41
43
49
51
53
54
56
57
60
61
52
63
64
67
68
69
70
71
75
62
76
77
13
86
90
91
94
95
96
97
101
106
112
113
117
118
119
122
124
16
47
125
133
135
136
9
137
23
19
45
140
141
143
109
146
147
6
17
21
104
149
12
89
116
66
157
160
142
148
161
165
173
28...

result:

ok q=100000

Test #36:

score: 0
Accepted
time: 78ms
memory: 11208kb

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:

2
3
4
5
6
7
12
14
15
17
18
21
23
25
26
28
29
30
32
34
36
43
46
48
35
51
52
57
59
60
64
66
68
71
72
74
78
82
84
81
85
87
89
90
91
94
95
16
20
97
98
33
101
102
103
105
107
109
110
112
113
114
118
117
119
120
122
123
125
115
128
130
132
134
138
139
141
143
144
146
147
148
151
153
159
161
162
163
22
104...

result:

ok q=100000

Test #37:

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

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:

3
4
5
7
9
12
13
14
15
17
20
21
23
24
27
29
32
33
34
35
36
41
26
43
44
45
46
47
48
50
51
53
56
58
60
62
65
69
72
79
81
82
83
85
91
93
97
99
100
105
106
109
112
115
119
120
123
125
126
131
132
133
80
135
136
138
49
139
140
141
142
145
147
148
150
66
151
152
155
162
165
166
168
174
177
178
179
183
184
...

result:

ok q=100000

Test #38:

score: 0
Accepted
time: 74ms
memory: 10940kb

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:

1
9
11
12
16
22
27
29
31
34
38
42
48
49
50
51
53
55
57
58
60
61
65
67
30
72
73
76
77
78
79
80
82
83
85
87
88
90
91
95
81
97
101
104
107
109
110
111
112
113
114
115
117
119
120
125
126
127
129
132
133
136
3
138
140
142
143
145
147
149
151
153
118
154
155
156
158
159
160
162
163
168
169
173
174
175
17...

result:

ok q=100000

Test #39:

score: 0
Accepted
time: 72ms
memory: 10740kb

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:

1
4
5
8
11
12
15
16
17
19
20
25
26
27
28
29
30
33
34
36
37
38
40
43
45
47
48
49
51
52
53
56
58
59
60
62
64
66
67
69
71
72
73
75
78
81
82
83
85
86
87
89
90
92
93
95
96
97
98
104
105
106
107
109
110
112
113
115
116
123
125
128
129
135
139
140
141
143
145
146
147
150
152
155
156
160
162
164
165
170
174...

result:

ok q=100000

Test #40:

score: 0
Accepted
time: 107ms
memory: 10772kb

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:

2

result:

ok q=100000

Test #41:

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

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:

83
3
5
11
19
26
36
38
45
50
25
56
61
35
66
71
81
105
113
9
97
43
74
111
118
22
46
91
117
8
104
76
47
24
7
69
29
18
32
94
1
12
20
58
70
87
100
79
86
23
123
126
128
142
144
150
51
67
116
13
15
53
131
146
151
62
34
135
147
28
108
63
93
124
136
140
137
145
59
92
64
95
134
48
143
149
68
154
157
158
55
15...

result:

ok q=100000

Test #42:

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

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
32
19
55
99
108
59
162
167
206
6
70
82
102
116
190
208
248
141
118
258
286
288
294
114
25
27
131
176
8
166
210
80
101
224
231
106
235
127
150
194
239
52
240
207
211
244
265
126
21
38
154
180
270
273
290
291
276
168
293
300
233
304
312
314
189
315
318
221
223
285
323
227
142
121
298
4
2
9
13
22
26
...

result:

ok q=100000

Test #43:

score: 0
Accepted
time: 79ms
memory: 10664kb

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
183
629
1073
374
820
314
351
760
239
258
14
274
460
138
584
685
704
797
84
101
328
396
431
530
102
547
2
184
308
372
343
87
333
377
426
439
448
533
148
169
548
197
594
615
51
354
497
398
630
357
205
154
75
59
115
117
133
196
261
104
1
124
237
303
403
446
217
440
449
125
212
450
451
452...

result:

ok q=100000

Test #44:

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

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:

109
555
1000
1443
258
104
117
239
550
563
685
704
995
1008
1129
1148
114
158
184
560
10
168
325
456
614
630
771
178
224
345
90
427
187
122
381
221
190
351
447
536
356
568
624
124
362
389
20
342
466
1
247
448
449
450
451
76
253
302
452
453
292
454
455
457
458
459
460
461
462
463
464
465
467
26
166
46...

result:

ok q=100000

Test #45:

score: 0
Accepted
time: 72ms
memory: 10340kb

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
223
667
1112
1554
370
816
1261
1703
1997
2146
2439
2587
2878
3027
3318
140
583
96
174
197
539
418
617
640
864
984
1028
1062
1085
1309
1426
1470
425
871
1316
1504
1527
1751
1758
278
724
1169
1611
1869
1913
1947
1970
2054
2194
2201
2311
2355
2389
2412
2496
2635
436
882
1327
1769
2212
2642
2653
2751
...

result:

ok q=100000

Test #46:

score: 0
Accepted
time: 80ms
memory: 10668kb

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
Memory 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:

2

result: