QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#800122#9632. 联通块A_programmer100 ✓941ms90552kbC++204.9kb2024-12-05 22:01:232024-12-05 22:01:24

Judging History

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

  • [2024-12-05 22:01:24]
  • 评测
  • 测评结果:100
  • 用时:941ms
  • 内存:90552kb
  • [2024-12-05 22:01:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int MAX_N = 2e5 + 5;
const int N = 3e5 + 5;

vector<int> g[maxn], H[MAX_N], tmpq[MAX_N], que[MAX_N];
int ST[17][maxn], U[maxn], V[maxn], dep[maxn], dfn[maxn], siz[maxn], idx;
void dfs(int u, int fu)
{
    ST[0][dfn[u] = ++idx] = fu, dep[u] = dep[fu] + 1, siz[u] = 1;
    for (int v : g[u]) if (v != fu) dfs(v, u), siz[u] += siz[v];
}

inline int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
inline int lca(int u, int v)
{
    if (u == v) return u;
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int d = __lg(v - u++);
    return get(ST[d][u], ST[d][v - (1 << d) + 1]);
}
inline int dis(int u, int v) { return dep[u] + dep[v] - (dep[lca(u, v)] << 1); }
inline pii merge(const pii &a, const pii &b)
{
    int au = a.first, av = a.second, bu = b.first, bv = b.second, cu = au, cv = av, nl = dis(au, av), tl;
    if (!au && !av) return b; if (!bu && !bv) return a;
    if ((tl = dis(bu, bv)) > nl) nl = tl, cu = bu, cv = bv;
    if ((tl = dis(au, bv)) > nl) nl = tl, cu = au, cv = bv;
    if ((tl = dis(bu, av)) > nl) nl = tl, cu = bu, cv = av;
    if ((tl = dis(au, bu)) > nl) nl = tl, cu = au, cv = bu;
    if ((tl = dis(av, bv)) > nl) nl = tl, cu = av, cv = bv;
    return make_pair(cu, cv);
}
pii S[17][maxn], vl[N];
inline pii query(int l, int r) { int k = __lg(r - l + 1); return merge(S[k][l], S[k][r - (1 << k) + 1]); }

vector<pii> tmp, Qd[MAX_N];
int stk[MAX_N], res[N], tp;

inline void dfs2(int u, int fu)
{
    stk[++tp] = u;
    for (int i : tmpq[u])
    {
        int d = dis(vl[i].first, vl[i].second);
        que[stk[tp - d]].emplace_back(d);
    }
    for (int v : H[u]) if (v != fu) dfs2(v, u);
    tp--;
}

bool vis[MAX_N];
int sz[MAX_N], son[MAX_N], rt, SS;
inline void findrt(int u, int fu)
{
    sz[u] = 1, son[u] = 0;
    for (int v : H[u])
        if (!vis[v] && v != fu) findrt(v, u), sz[u] += sz[v], son[u] = max(son[u], sz[v]);
    son[u] = max(son[u], SS - sz[u]);
    if (son[u] < son[rt]) rt = u;
}

int dt[MAX_N], dv[N], tt[MAX_N], tv[N], dpt[MAX_N];
inline void DFS(int u, int fu)
{
    dpt[u] = dpt[fu] + 1, dt[++dt[0]] = tt[++tt[0]] = u; for (int d : que[u]) dv[++dv[0]] = tv[++tv[0]] = dpt[u] + d;
    for (int v : H[u]) if (!vis[v] && v != fu) DFS(v, u);
}
void Solve(int u)
{
    tt[0] = tv[0] = dpt[u] = 0, vis[u] = 1;
    for (int v : H[u])
    {
        if (vis[v]) continue;
        dt[0] = dv[0] = 0, DFS(v, u);
        sort(dv + 1, dv + dv[0] + 1);
        for (int i = 1; i <= dt[0]; i++)
            for (pii nw : Qd[dt[i]]) res[nw.second] -= upper_bound(dv + 1, dv + dv[0] + 1, nw.first - dpt[dt[i]]) - dv - 1;
    }
    for (int d : que[u]) tv[++tv[0]] = d; tt[++tt[0]] = u;
    sort(tv + 1, tv + tv[0] + 1);
    for (int i = 1; i <= tt[0]; i++)
        for (pii nw : Qd[tt[i]]) res[nw.second] += upper_bound(tv + 1, tv + tv[0] + 1, nw.first - dpt[tt[i]]) - tv - 1;
    for (int v : H[u]) if (!vis[v]) rt = 0, SS = sz[v], findrt(v, 0), Solve(rt);
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    int cid, n, m, q;
    cin >> cid >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        U[i] = u, V[i] = v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        H[n + i] = {u, v}, H[u].emplace_back(n + i), H[v].emplace_back(n + i);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) S[0][dfn[i]] = make_pair(i, i);
    for (int i = 1; i <= 16; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++)
        ST[i][j] = get(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
    for (int i = 1; i <= 16; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++)
        S[i][j] = merge(S[i - 1][j], S[i - 1][j + (1 << (i - 1))]);
    
    int ID = 0;
    while (m--)
    {
        int k; cin >> k; tmp.clear();
        tmp.emplace_back(make_pair(1, 1)), tmp.emplace_back(make_pair(n + 1, 0));
        for (int i = 1; i <= k; i++)
        {
            int eid; cin >> eid;
            int x = dep[U[eid]] > dep[V[eid]] ? U[eid] : V[eid];
            tmp.emplace_back(make_pair(dfn[x], 1)), tmp.emplace_back(make_pair(dfn[x] + siz[x], 0));
        }
        sort(tmp.begin(), tmp.end());

        int lst = 1; tp = 0;
        for (pii nw : tmp)
        {
            if (lst < nw.first) vl[stk[tp]] = merge(vl[stk[tp]], query(lst, nw.first - 1)), lst = nw.first;
            if (nw.second) stk[++tp] = ++ID; else tp--;
        }
    }
    m = ID; for (int i = 1; i <= m; i++) tmpq[dep[vl[i].first] > dep[vl[i].second] ? vl[i].first : vl[i].second].emplace_back(i);
    tp = 0, dfs2(1, 0);
    for (int i = 1; i <= q; i++)
    {
        int u, r; cin >> u >> r, r <<= 1;
        Qd[u].emplace_back(make_pair(r, i));
    }

    SS = (n << 1) - 1, son[rt = 0] = 0x3f3f3f3f, findrt(1, 0);
    Solve(rt); for (int i = 1; i <= q; i++) cout << res[i] << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 26472kb

input:

1 500 25 500
160 300
95 345
131 498
259 359
400 394
445 137
75 145
126 185
86 336
44 98
271 32
73 227
2 1
39 420
487 38
356 240
447 193
70 26
46 171
436 272
260 485
393 66
297 351
192 88
326 245
174 416
4 9
399 194
58 350
256 176
376 248
2 59
77 7
59 148
258 173
352 34
9 320
221 244
3 1
284 193
335 ...

output:

456
450
12
500
153
8
4
33
3
10
432
500
420
396
93
228
2
500
20
340
6
475
1
0
13
256
500
308
396
15
421
500
500
500
32
67
450
128
500
153
420
2
0
432
18
6
92
308
85
500
0
1
33
500
8
228
500
1
367
475
228
450
500
432
420
218
142
20
500
8
14
500
500
218
500
341
456
450
37
4
0
1
1
162
228
500
500
99
148...

result:

ok 500 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 26352kb

input:

1 500 25 500
107 126
144 226
2 94
361 236
47 21
11 277
387 350
45 70
274 258
159 95
104 78
349 419
251 66
164 435
181 46
55 24
355 393
404 234
306 153
191 308
54 74
106 36
58 84
45 14
73 348
114 163
346 16
391 74
6 4
320 70
254 482
469 36
118 212
17 27
85 148
109 28
18 48
26 19
172 176
312 208
11 18...

output:

429
18
171
447
326
14
500
500
2
347
24
308
232
395
369
447
500
101
16
470
447
149
447
424
10
326
52
500
470
40
42
500
500
210
470
422
161
470
500
0
6
20
161
0
177
42
308
104
500
46
500
1
0
231
447
8
22
422
115
3
500
447
30
1
500
59
0
500
3
2
500
0
500
8
2
54
395
53
447
1
500
114
422
106
231
3
232
2
...

result:

ok 500 lines

Test #3:

score: 10
Accepted
time: 0ms
memory: 26412kb

input:

1 500 25 500
189 213
447 219
35 251
109 395
46 18
169 115
36 57
413 28
66 8
489 124
409 10
118 15
143 150
256 461
317 273
22 29
107 3
113 133
88 109
478 88
158 150
160 41
233 435
238 166
89 137
77 250
50 101
134 84
327 172
107 151
122 176
70 282
120 146
361 150
450 64
5 16
93 56
101 175
373 194
426 ...

output:

95
8
0
18
36
469
0
500
453
403
442
53
500
500
500
10
2
10
3
469
95
366
5
227
154
43
48
4
23
470
432
88
12
0
3
357
500
396
0
0
59
470
59
154
0
348
3
231
348
0
348
469
5
6
1
442
500
475
38
0
61
27
211
442
213
147
21
397
4
7
469
475
147
9
43
442
396
500
43
67
231
12
18
357
357
20
470
500
80
192
6
17
1
...

result:

ok 500 lines

Test #4:

score: 10
Accepted
time: 3ms
memory: 26360kb

input:

1 500 25 500
26 34
239 252
92 80
252 254
308 304
33 44
395 408
98 105
245 237
9 6
490 494
84 89
452 458
387 397
15 11
306 313
120 115
138 149
263 272
264 266
320 323
91 88
204 191
344 334
493 482
255 259
238 234
282 292
213 225
346 357
191 197
434 445
492 495
136 137
71 78
442 449
477 464
196 188
12...

output:

335
500
97
240
500
500
9
19
368
0
500
172
500
500
196
500
1
213
368
339
500
500
318
500
20
247
279
500
65
426
500
42
2
500
56
187
30
500
500
149
500
500
500
500
302
329
500
0
500
500
0
500
0
380
339
55
500
500
500
208
265
500
23
308
500
317
318
44
307
500
500
380
420
314
193
500
500
500
500
348
500
...

result:

ok 500 lines

Test #5:

score: 10
Accepted
time: 0ms
memory: 24332kb

input:

1 500 25 500
413 417
57 48
425 422
35 46
144 149
429 435
113 123
350 342
364 360
290 303
68 81
178 168
280 281
160 165
102 104
488 477
229 237
133 129
129 119
196 187
190 177
225 226
405 414
117 124
180 177
153 140
450 457
206 211
32 43
13 14
183 188
361 363
398 388
149 155
185 175
410 404
254 266
1...

output:

246
500
500
500
500
292
175
500
500
419
32
305
500
500
500
164
500
257
500
133
500
500
419
500
330
500
292
296
399
500
346
500
0
500
376
500
247
41
500
500
500
330
19
500
163
252
500
80
500
500
500
500
152
500
409
0
18
500
457
366
500
475
9
3
500
3
500
500
500
500
500
113
500
500
500
3
500
0
58
151
...

result:

ok 500 lines

Test #6:

score: 10
Accepted
time: 6ms
memory: 26356kb

input:

1 500 25 500
409 413
381 371
55 47
395 400
497 487
305 302
168 166
405 395
202 191
340 337
422 421
449 443
191 179
422 431
297 289
382 384
269 280
495 483
110 121
189 196
277 289
141 149
400 412
310 313
47 54
50 46
237 241
460 467
92 93
494 489
228 216
146 156
43 34
328 327
298 308
170 181
6 8
158 1...

output:

500
62
500
96
500
16
470
500
21
398
81
500
105
390
398
500
500
112
363
268
4
500
267
500
500
500
500
500
1
500
500
18
390
378
500
500
13
117
52
500
500
500
500
212
500
14
27
500
396
391
63
375
500
222
189
18
500
312
500
500
500
500
279
500
107
500
500
500
312
500
500
219
500
279
195
99
252
29
500
50...

result:

ok 500 lines

Test #7:

score: 10
Accepted
time: 3ms
memory: 26340kb

input:

1 500 25 500
172 183
392 411
20 24
330 339
146 182
58 67
61 111
381 419
114 96
213 261
187 162
260 287
144 109
108 72
90 81
217 181
148 166
365 393
280 300
368 334
362 361
149 93
209 212
208 169
200 144
49 10
50 38
218 160
350 370
327 278
249 218
38 44
124 179
46 44
280 251
415 441
462 484
468 494
2...

output:

66
98
456
500
223
340
169
216
434
51
8
33
16
208
77
78
500
173
133
500
192
0
195
141
107
88
500
96
20
190
374
144
80
500
360
318
500
441
14
500
150
5
500
220
234
14
13
58
8
9
500
0
158
0
281
500
304
334
340
263
15
307
277
318
400
500
0
71
15
426
2
10
0
500
159
202
225
132
27
3
25
500
157
99
475
0
11...

result:

ok 500 lines

Test #8:

score: 10
Accepted
time: 0ms
memory: 26344kb

input:

1 500 25 500
170 187
162 177
145 94
366 379
9 14
354 397
427 404
289 246
67 106
93 86
459 429
148 193
228 225
354 395
151 111
458 405
243 280
449 477
483 493
464 489
27 24
252 271
166 141
344 301
12 6
410 378
6 2
54 98
396 346
120 175
400 437
109 97
86 130
264 227
381 380
155 179
407 379
264 302
19 ...

output:

500
2
500
67
343
475
128
197
5
219
430
500
314
293
409
53
351
12
122
351
444
37
475
8
39
62
250
253
343
471
338
12
270
475
500
31
500
307
74
500
289
22
0
500
500
197
500
8
500
427
7
500
500
22
191
0
343
430
500
300
44
43
2
47
26
338
341
6
15
2
7
92
237
253
13
79
216
29
96
301
475
430
9
13
2
500
19
2...

result:

ok 500 lines

Test #9:

score: 10
Accepted
time: 3ms
memory: 26472kb

input:

1 500 25 500
209 246
129 88
12 14
320 271
296 300
48 55
155 156
386 406
95 85
139 85
152 144
370 398
412 369
88 142
154 142
484 457
170 113
439 425
363 332
18 30
302 279
277 316
276 255
249 260
366 345
308 357
3 11
364 368
466 413
383 374
18 17
479 440
88 86
80 102
118 92
205 214
498 450
430 388
173...

output:

202
251
500
126
157
346
295
44
500
5
56
123
329
4
64
392
465
264
298
500
4
5
154
13
249
6
212
289
39
64
500
412
36
10
465
23
1
81
2
138
500
500
304
500
0
251
404
425
130
500
0
11
369
288
32
241
271
500
102
241
128
460
0
384
401
228
66
5
13
9
124
80
384
427
21
253
384
11
249
355
86
1
154
332
276
3
39...

result:

ok 500 lines

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #10:

score: 10
Accepted
time: 3ms
memory: 26852kb

input:

2 2000 50 2000
1423 1355
1791 890
145 1295
637 1018
413 1025
1127 649
955 904
108 55
893 971
1952 1944
400 41
453 357
731 95
291 368
40 1442
899 1022
1406 1862
547 1388
577 102
1035 1183
196 881
286 882
1022 1078
832 110
272 626
1326 197
636 569
29 19
188 241
219 82
1237 1334
44 53
113 44
354 9
132 ...

output:

5
2000
187
8
2000
65
323
2000
254
5
1449
2
188
146
1920
1704
2000
113
1664
47
31
37
3
984
2000
0
1920
17
0
373
1941
22
635
1
363
673
929
2000
361
282
0
3
1941
1402
2
1805
1878
934
1312
0
556
1402
2000
2000
1068
673
975
984
933
0
11
1068
2000
753
0
0
1
939
5
2000
1704
1711
2000
25
9
1676
2
1878
29
34...

result:

ok 2000 lines

Test #11:

score: 10
Accepted
time: 6ms
memory: 29028kb

input:

2 2000 50 2000
1142 1744
1321 1376
917 256
1413 493
422 199
1187 686
197 293
1846 1350
142 1535
197 114
1012 1847
468 591
378 291
255 79
1766 848
555 536
859 1098
727 96
1746 1038
1710 1684
273 407
336 1421
678 685
355 1602
648 1041
1071 9
1988 82
441 492
38 40
564 669
185 352
503 1961
472 1807
49 6...

output:

0
1915
0
4
753
2
1004
1389
83
331
1
1303
1212
1183
1915
220
13
2
1444
14
22
441
573
1821
131
0
1110
2000
448
8
746
168
201
1915
7
9
23
1863
1
11
2000
1371
1558
1004
22
245
1883
2000
1004
571
2000
0
307
1639
1883
2000
0
6
758
1858
1863
42
2000
1710
141
23
1832
2
88
294
2000
83
115
737
1453
48
1697
16...

result:

ok 2000 lines

Test #12:

score: 10
Accepted
time: 6ms
memory: 26924kb

input:

2 2000 50 2000
835 1292
1674 169
145 139
1267 570
415 1055
487 168
1274 788
58 41
115 414
1736 927
123 525
790 1368
902 1434
1916 1249
1019 1351
382 642
1837 1542
1759 774
971 1940
475 709
1457 1079
255 138
1479 1331
1884 431
346 1954
505 64
208 1361
662 129
1842 1385
251 952
1436 1456
60 1804
588 1...

output:

2000
2000
0
1789
1705
268
452
17
1705
2000
369
30
2000
1
1849
2000
0
2000
1870
2
1684
1892
2000
8
1
29
2000
2000
1910
18
2000
1910
18
2000
392
655
191
2000
1031
1419
2000
1218
2000
2000
2000
1710
2000
2000
1831
1849
12
498
712
2000
1798
9
0
155
294
2000
2000
1910
133
9
20
1667
2000
1833
2000
1870
43...

result:

ok 2000 lines

Test #13:

score: 10
Accepted
time: 0ms
memory: 28956kb

input:

2 2000 50 2000
1975 1973
1010 1000
1526 1536
271 257
193 202
1450 1455
1684 1699
1 2
698 699
799 788
1186 1187
917 921
534 531
1252 1254
1803 1811
627 621
186 191
818 813
1703 1712
616 625
1491 1501
567 560
882 892
1780 1769
1190 1186
1377 1392
1541 1555
660 672
400 411
167 180
1726 1723
1874 1883
3...

output:

611
110
2000
583
2000
106
2000
2000
2000
1906
1122
2000
1592
2000
2000
2000
2000
1219
518
2000
1933
1875
1837
2000
1749
650
2000
2000
142
2000
2000
1291
963
2000
2000
1897
2000
2000
533
2000
1900
1164
2000
2000
2000
2000
1909
2000
2000
1647
2000
1179
97
2000
1024
58
50
2000
1728
2000
1844
354
2000
2...

result:

ok 2000 lines

Test #14:

score: 10
Accepted
time: 3ms
memory: 31072kb

input:

2 2000 50 2000
491 501
1680 1681
1631 1646
1581 1577
1895 1901
1281 1280
667 662
1720 1722
696 708
918 919
1352 1357
213 221
255 245
1590 1599
1070 1068
96 83
497 509
401 399
1320 1314
418 426
704 719
1016 1006
1606 1607
1498 1496
47 40
908 904
1801 1796
1312 1316
1717 1720
520 527
424 423
1087 1078...

output:

1009
2000
2000
1468
1277
2000
2000
2000
2000
1728
2000
2000
2000
818
1372
541
2000
2000
2000
1158
2000
7
2000
1495
1656
2000
1946
207
708
1318
2000
1490
1948
1348
585
1728
2000
2000
145
1166
1292
2000
620
2000
2000
2000
1090
2000
2000
2000
1250
1001
2000
2000
769
1845
1284
2000
2000
1292
2000
1816
2...

result:

ok 2000 lines

Test #15:

score: 10
Accepted
time: 7ms
memory: 31076kb

input:

2 2000 50 2000
434 448
421 416
1268 1263
561 576
1132 1146
653 640
870 862
695 703
853 840
1064 1067
96 90
1430 1442
898 904
1607 1598
1316 1318
1238 1227
685 687
437 442
1260 1275
686 699
1388 1402
1993 1994
1237 1236
1984 1985
1387 1390
1711 1704
309 322
1896 1906
1834 1821
1376 1378
1304 1298
108...

output:

6
421
2000
2000
2000
2000
2000
2000
2000
2000
2000
1504
2000
2000
1083
2000
1116
2000
2000
1513
2000
2000
1670
1720
2000
1092
1055
2000
2000
2000
490
1098
2000
2000
2000
2000
1761
1474
933
1086
2000
1287
16
84
380
1782
2000
2000
460
54
2000
1145
2000
1393
1669
392
943
1791
561
1264
561
859
2000
2000...

result:

ok 2000 lines

Test #16:

score: 10
Accepted
time: 10ms
memory: 26952kb

input:

2 2000 50 2000
1536 1490
1623 1616
631 615
23 67
256 197
1800 1735
1164 1278
1144 1038
894 960
16 122
402 466
75 105
757 662
683 761
1162 1057
1139 1155
1605 1649
713 663
1047 991
845 860
925 841
1899 1870
1068 977
579 477
1165 1252
1741 1828
1397 1447
877 977
1391 1491
181 229
1614 1629
659 576
139...

output:

922
274
417
995
351
2000
1675
730
307
645
51
219
1
35
2000
1525
2000
3
2000
1687
1256
1368
669
51
312
105
1022
1368
2000
1194
2000
22
1742
40
3
47
194
727
2000
36
1604
261
363
2000
1150
16
922
57
1690
1950
717
503
1
23
444
1053
60
3
1112
48
1514
79
33
2000
168
381
0
2000
1138
168
402
856
380
1495
19...

result:

ok 2000 lines

Test #17:

score: 10
Accepted
time: 7ms
memory: 26924kb

input:

2 2000 50 2000
1059 1149
1395 1302
613 566
1443 1381
1975 1896
1839 1917
1346 1256
1027 920
1219 1309
1270 1340
1742 1682
42 51
1817 1729
260 175
683 653
1024 1106
1023 942
1735 1690
1645 1551
387 501
582 656
856 822
380 268
643 618
1285 1297
429 379
641 750
446 523
1205 1312
1412 1424
1768 1883
151...

output:

1284
1270
822
387
2
1947
2000
2000
1605
349
656
333
804
837
372
176
745
3
2000
1069
329
2000
1265
317
498
287
890
329
34
1877
1454
2000
1850
83
61
1947
106
2
837
1862
309
1247
2000
1634
423
1341
441
2000
129
1950
1590
73
1538
66
2000
1816
1705
44
504
1756
426
482
36
123
178
1398
132
1375
924
1097
10...

result:

ok 2000 lines

Test #18:

score: 10
Accepted
time: 5ms
memory: 29036kb

input:

2 2000 50 2000
1545 1576
413 412
1120 1136
1186 1142
1727 1839
1034 1051
1239 1183
543 591
1874 1858
1232 1174
475 401
853 933
1266 1348
1008 1007
1395 1366
952 891
1188 1165
1701 1726
1243 1229
521 450
552 544
673 690
696 750
682 783
1868 1800
1322 1426
905 897
677 756
978 1035
965 969
1448 1346
41...

output:

2000
9
467
543
18
1586
258
41
1058
1060
1124
2000
5
2000
138
1675
192
159
1718
1008
22
292
2000
956
2000
2000
1008
121
2000
33
153
963
2000
2000
30
2000
2000
1144
731
251
2000
82
2000
1641
53
1229
49
78
861
956
1633
28
2000
249
2000
34
965
1157
498
753
156
487
565
518
2000
612
2000
229
1806
2000
160...

result:

ok 2000 lines

Subtask #3:

score: 15
Accepted

Test #19:

score: 15
Accepted
time: 357ms
memory: 88464kb

input:

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

output:

7116
18702
30685
89626
91900
68029
99856
24514
99856
21550
958
63513
67890
69627
81017
45120
25573
23339
99856
48788
69094
79557
76332
41540
65799
99856
90842
99856
32381
48306
69788
25982
99856
69144
99856
17666
77905
97107
86289
99856
85158
66764
63052
16065
95112
30243
64004
68333
76813
99856
910...

result:

ok 100000 lines

Test #20:

score: 15
Accepted
time: 349ms
memory: 90552kb

input:

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

output:

10015
74652
50243
65090
73508
75718
99856
99856
99856
95576
29751
14262
57510
57264
99856
5937
38610
2328
77394
99856
89756
54138
80485
86024
32182
99856
59748
48953
66530
99856
84516
58145
99856
63032
80970
99856
99856
3945
99856
93385
12520
50127
87819
89913
47464
99856
81560
81019
53395
9623
3767...

result:

ok 100000 lines

Test #21:

score: 15
Accepted
time: 355ms
memory: 89328kb

input:

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

output:

99856
99856
99856
99856
50718
99856
69275
24315
89556
87309
50041
93165
53745
25011
99856
42078
31147
99856
99856
53269
99856
70462
71903
15651
51108
77294
42794
76694
20334
99856
85737
88288
71878
46679
7090
56259
41696
54253
13634
99856
99856
35761
83738
63697
53828
38779
24648
88262
54147
88185
3...

result:

ok 100000 lines

Test #22:

score: 15
Accepted
time: 337ms
memory: 90016kb

input:

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

output:

23346
93425
10413
100000
48330
100000
36951
80129
17434
100000
77500
100000
100000
118
30571
10398
85975
84256
24721
52893
100000
20739
24371
65027
93697
51684
100000
74085
99062
76826
100000
16064
67828
51049
51291
3299
59621
100000
32754
34095
26308
64825
38751
100000
76043
90337
71601
32142
95533...

result:

ok 100000 lines

Test #23:

score: 15
Accepted
time: 339ms
memory: 89852kb

input:

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

output:

76843
59847
56242
37475
100000
100000
50097
57146
95889
68810
93468
91438
82945
85819
75690
100000
86824
100000
29266
100000
21464
80995
1636
100000
32757
83791
98372
28301
100000
100000
74010
100000
69931
2766
24305
45797
100000
31395
100000
56939
73636
91193
100000
48603
100000
89533
65137
100000
...

result:

ok 100000 lines

Test #24:

score: 15
Accepted
time: 330ms
memory: 89200kb

input:

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

output:

100000
100000
98884
22455
3777
99477
74993
69573
77981
92696
90334
37440
100000
5712
100000
45897
45667
100000
100000
88979
42527
89482
100000
64273
89918
65626
37836
37387
100000
57577
46959
13268
40920
33974
62514
51743
100000
81962
76080
93652
92825
51070
100000
79023
79748
83708
24836
72715
3455...

result:

ok 100000 lines

Test #25:

score: 15
Accepted
time: 376ms
memory: 89924kb

input:

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

output:

87217
82002
100000
59429
74730
100000
78476
100000
62492
35730
3978
82420
66389
100000
82797
74837
86444
84263
69491
77263
60822
21044
100000
56671
53972
100000
78354
94901
19671
79256
22709
82427
42536
35257
100000
76139
100000
1431
66396
73077
93268
60577
81767
60303
28012
64072
71495
31360
100000...

result:

ok 100000 lines

Test #26:

score: 15
Accepted
time: 379ms
memory: 88628kb

input:

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

output:

100000
67436
79064
16131
81070
100000
58268
28248
100000
82149
65947
100000
59054
72152
70142
100000
100000
75403
100000
64722
100000
38772
21518
115
69310
47232
100000
8098
91011
55812
20884
87262
82372
52600
63500
100000
74300
100000
62227
74299
100000
93722
1199
57311
60543
100000
33144
100000
27...

result:

ok 100000 lines

Test #27:

score: 15
Accepted
time: 380ms
memory: 89664kb

input:

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

output:

83203
100000
66244
100000
56348
23615
100000
100000
100000
7549
84225
100000
86951
62679
87129
4189
74949
100000
78906
73386
58608
74219
61534
80287
30712
94467
100000
63398
35709
10548
64162
41104
77343
69569
38819
16872
53540
88081
88053
89054
38595
18183
52086
42475
52097
71060
100000
67187
14653...

result:

ok 100000 lines

Subtask #4:

score: 25
Accepted

Test #28:

score: 25
Accepted
time: 364ms
memory: 65768kb

input:

4 100000 50000 100000
83534 91958
44638 83107
30555 37613
47320 11817
17145 22205
3821 9581
12272 20812
293 1463
2550 2641
179 16579
28031 50662
15687 18932
6940 24780
31978 15599
17053 41795
56716 41026
32760 49030
96468 81779
44875 24089
67246 61768
44737 15873
64089 12670
7530 36388
68738 5284
32...

output:

21524
1
29017
1273
0
43127
49904
5
46274
50
54
5332
48504
33938
46141
100000
1097
1
4
473
29145
47147
49975
249
6436
385
100000
11564
49165
100000
5048
49968
21545
7628
100000
49957
27075
33909
194
34154
1
35144
100000
2
747
48824
49904
129
28
0
38866
45922
95
138
100000
100000
30070
0
1
51
1361
136...

result:

ok 100000 lines

Test #29:

score: 25
Accepted
time: 386ms
memory: 64460kb

input:

4 100000 50000 100000
77842 60502
68603 52317
31757 38542
84992 10892
9615 66890
24220 47013
43637 21910
64734 89003
82416 48686
35202 53940
71978 23016
10171 9981
45365 8667
15334 4983
96236 24780
64584 30356
56468 75646
27829 58014
47072 61318
2112 11409
32125 11754
12997 36312
40004 76860
59138 1...

output:

3
2
11352
39
49999
49823
55
1031
6345
11
45598
100000
2296
3651
100000
100000
28916
0
10
100000
80
100000
49962
49416
49910
1
100000
1485
2
100000
49966
49873
45884
28916
100000
11
100000
10722
47500
20
100000
124
12
100000
49952
2418
993
1
6
49802
262
100000
10099
7
2
11629
29224
49975
39534
100000...

result:

ok 100000 lines

Test #30:

score: 25
Accepted
time: 369ms
memory: 64720kb

input:

4 100000 50000 100000
1533 60
37566 46236
120 6020
26515 4541
87200 96476
99247 10073
10680 58234
51534 21685
71470 84409
85346 38908
2079 1572
279 13244
19816 6290
41410 45925
65690 96134
57550 50651
11322 24039
63056 69621
50998 62596
11627 12486
21194 29838
65222 14474
73767 98601
78758 78590
405...

output:

34
10
3351
2472
49515
15514
11193
12
49749
19828
492
3466
48567
44667
48470
813
5
54
100000
48414
100000
100000
3699
21596
7228
3
18159
24732
49992
39
6
1922
796
123
1
13018
2652
4
46671
9704
8205
14
100000
100000
48215
168
7696
1110
3234
272
2
100000
49221
48567
100000
4
49805
100000
100000
44659
4...

result:

ok 100000 lines

Test #31:

score: 25
Accepted
time: 517ms
memory: 68248kb

input:

4 100000 50000 100000
32448 32450
10131 10125
67127 67120
53244 53250
24856 24862
71953 71950
90216 90214
67227 67230
99550 99557
26703 26708
88211 88201
27040 27032
2724 2717
90632 90629
76881 76879
51851 51845
4343 4351
76105 76102
8472 8476
67900 67905
36064 36067
40447 40448
7701 7707
66772 6676...

output:

100000
3162
100000
30230
100000
100000
19783
12186
100000
100000
100000
100000
48918
45238
100000
100000
5609
100000
6077
100000
100000
19326
27346
100000
41334
100000
5527
100000
36445
100000
100000
100000
100000
37415
33257
31514
100000
100000
100000
100000
16402
36623
100000
100000
7010
100000
10...

result:

ok 100000 lines

Test #32:

score: 25
Accepted
time: 505ms
memory: 68232kb

input:

4 100000 50000 100000
94678 94685
1744 1741
3208 3218
13379 13386
39895 39891
99322 99330
88139 88148
7647 7640
60107 60102
47967 47977
19560 19552
74004 74009
98910 98901
27190 27187
17972 17973
21702 21706
23750 23745
90394 90396
44431 44425
76316 76324
46516 46512
35431 35434
81037 81042
58554 58...

output:

100000
100000
12982
100000
100000
15485
100000
46829
15847
6507
100000
42361
100000
100000
100000
100000
42721
41385
25323
100000
43909
22456
36571
31282
4480
100000
48327
100000
100000
100000
100000
17675
100000
43125
100000
35612
26546
31715
29345
100000
100000
100000
33055
13681
100000
30510
1000...

result:

ok 100000 lines

Test #33:

score: 25
Accepted
time: 510ms
memory: 68336kb

input:

4 100000 50000 100000
13347 13339
93472 93465
11588 11598
83781 83771
54305 54298
88935 88933
67285 67282
79181 79189
93584 93577
68025 68022
52603 52594
31534 31543
89422 89419
14893 14896
28485 28486
76814 76817
52443 52442
80504 80512
15821 15819
92174 92172
24309 24299
43107 43115
59039 59036
17...

output:

100000
27002
27859
100000
36217
17050
100000
100000
9305
100000
45031
39493
44602
35762
100000
48165
49163
100000
10902
11606
17379
48835
100000
12392
15215
46009
19891
100000
48647
100000
100000
100000
100000
37139
100000
100000
100000
100000
100000
100000
46329
100000
14107
638
100000
21486
41333
...

result:

ok 100000 lines

Test #34:

score: 25
Accepted
time: 473ms
memory: 66116kb

input:

4 100000 50000 100000
27220 27613
80775 81268
26467 26663
44355 44572
14754 14751
80229 79684
4637 5185
14119 14337
32417 32329
98527 98598
61618 61605
43459 43613
21764 21206
59729 59471
62820 63177
26925 27348
23195 22936
31849 32039
23308 23246
11513 10993
80697 80441
25456 25350
82055 82624
1125...

output:

972
25600
49922
1759
640
2509
2789
822
31950
10300
38849
5933
100000
47412
46657
35821
6550
49494
2446
36967
25393
1873
47177
777
34240
100000
39986
32996
49015
17467
468
34140
10565
2
14570
144
907
792
825
11538
8169
39788
31026
34373
29877
2994
177
2206
32283
25383
9106
46596
20720
25062
100000
10...

result:

ok 100000 lines

Test #35:

score: 25
Accepted
time: 493ms
memory: 64748kb

input:

4 100000 50000 100000
4059 3474
43097 42893
48468 48283
82624 82818
73379 72972
75244 74728
20337 19911
14627 14498
2757 3229
33229 33025
56306 56660
40016 40100
99001 99580
3094 2587
67536 67564
76345 75987
79149 79076
65601 65131
5268 5575
56760 56228
66571 67189
57942 57675
80242 80787
9335 9145
...

output:

31904
3726
34001
1517
1054
20674
21530
1158
19047
3948
35974
2493
100000
100000
45
36041
13167
39708
39814
9192
28770
5110
1223
114
473
9381
950
3957
3270
32871
34081
100000
38857
12319
634
24869
49898
4325
143
13449
5913
4853
9859
35109
13917
47876
27702
100000
4758
43357
37258
49879
10
13192
47337...

result:

ok 100000 lines

Test #36:

score: 25
Accepted
time: 500ms
memory: 65092kb

input:

4 100000 50000 100000
73044 73454
93691 93415
71325 71523
68734 69170
34031 33907
42247 41922
63665 63397
38988 39408
78269 78776
60822 60565
25802 25313
43737 44065
15601 15188
63478 63945
9357 9227
77914 77377
42493 43010
98915 98658
22217 22629
92131 92251
51899 51691
58874 58483
38940 39255
7896...

output:

19679
12051
1216
2151
12114
39706
127
718
22606
20481
14223
49946
100000
3278
37654
25905
18704
7472
3937
42656
14004
33286
1036
34
13240
47117
44906
28950
49794
3126
37025
39082
141
21756
49005
33525
3736
2637
243
6352
11
10036
2921
27496
28673
771
48153
50000
45654
6753
12682
2007
41221
100000
420...

result:

ok 100000 lines

Subtask #5:

score: 35
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #37:

score: 35
Accepted
time: 454ms
memory: 65888kb

input:

5 100000 316 100000
23794 39146
22697 66741
94669 68889
17521 61338
63842 52825
20565 88425
90608 20936
24876 12335
29694 15463
16163 43174
19793 25593
15593 17908
66865 13018
33219 87021
3059 1900
17252 56350
57600 49109
19330 30283
27034 41128
86135 49290
51688 15190
26660 8919
56502 28237
23935 2...

output:

9
77201
145
43
605
253
98951
61913
5
62604
99856
1
3474
6
254
68182
85646
66037
71133
98951
69902
92496
49889
827
176
18564
89526
5225
0
6198
8674
2
98951
99856
31
87828
4
99294
99856
89526
53
5104
6216
8
99856
401
99856
297
224
99280
13004
98161
88
99221
98312
25301
76038
99476
397
84341
14
1236
62...

result:

ok 100000 lines

Test #38:

score: 35
Accepted
time: 547ms
memory: 69648kb

input:

5 100000 316 100000
35731 35733
69762 69754
54042 54052
15451 15454
71859 71863
24192 24184
2157 2151
52705 52714
52175 52179
61591 61599
18579 18589
16159 16166
43610 43607
76431 76427
23761 23760
73401 73411
85035 85027
3606 3611
25136 25144
38652 38650
13315 13321
87617 87621
49441 49438
66810 66...

output:

67311
84226
66186
63413
37688
99856
99856
54779
78659
35330
79954
93458
99856
99856
99856
99856
35575
99856
6258
99856
99856
99856
86077
99856
99856
99856
27500
99856
99856
99856
99856
9404
99856
99856
99856
99856
62652
78230
99856
99856
99856
99856
59121
11817
9762
99856
20413
99856
96031
76356
998...

result:

ok 100000 lines

Test #39:

score: 35
Accepted
time: 564ms
memory: 69064kb

input:

5 100000 316 100000
24614 24619
23530 23535
13765 13768
89312 89316
72539 72532
10578 10586
25273 25282
77189 77187
76307 76308
49978 49969
52052 52042
49381 49389
32217 32226
11509 11518
83356 83349
19211 19210
96441 96450
46785 46784
33860 33866
40154 40144
38773 38772
7809 7813
70596 70587
94415 ...

output:

78111
99856
99856
99856
69716
78373
99856
99856
31540
99856
99856
99856
8063
96267
99856
99856
82843
99856
15407
99856
86902
99856
71229
99856
99856
99856
21583
82975
34285
99856
99856
99856
99856
99856
31643
99856
78813
99856
99222
37516
99856
99856
99856
95745
99856
74835
99856
99856
79385
99856
4...

result:

ok 100000 lines

Test #40:

score: 35
Accepted
time: 532ms
memory: 65284kb

input:

5 100000 316 100000
36479 35833
80324 80288
82999 83228
53545 52965
90992 91494
20365 20825
52606 52480
35974 36395
58375 58828
3015 3171
65255 64898
45751 46361
48843 48437
16121 16104
52066 52326
32467 32932
42315 41959
78170 77938
90063 89777
68829 68753
53217 52623
18172 18426
3206 3566
18692 18...

output:

66167
92854
222
70717
36004
75062
60795
23132
74669
780
66437
57970
1328
5179
99856
968
2251
806
44460
92812
72758
85637
99856
15037
48075
72815
99856
55200
44481
42588
49168
70514
8926
80942
47116
20771
9180
99856
53048
66405
53088
5096
99856
48057
2118
5154
99856
65831
2889
59337
9251
30831
1961
9...

result:

ok 100000 lines

Test #41:

score: 35
Accepted
time: 542ms
memory: 65812kb

input:

5 100000 316 100000
99235 98853
93750 94079
89263 89894
57418 57162
95350 95339
54893 54971
98581 98244
94634 94572
79442 79900
29966 29644
12234 11894
6925 7011
36834 36443
19889 20156
65624 66160
30470 30173
33541 33452
10962 10953
15953 15390
27747 27295
25219 25845
39767 39248
39507 39549
17382 ...

output:

64440
54552
69308
71683
21776
93760
21173
22
69360
43674
26718
59287
92421
50894
13606
577
99856
11100
64468
26578
52504
92607
81859
1410
65612
50751
2292
42297
99856
40968
5984
93111
25527
25852
84089
40502
5
99856
70599
1728
73283
72477
23106
54962
32346
26214
82975
352
34249
17413
51884
48266
799...

result:

ok 100000 lines

Test #42:

score: 35
Accepted
time: 458ms
memory: 66024kb

input:

5 100000 20 100000
61601 78976
8480 35996
2900 4490
32402 46468
14766 5277
8678 8671
62062 39866
90406 60873
11397 13581
15644 9290
3154 36203
16569 14450
11131 1891
10666 7022
3627 14468
35237 69884
24649 35216
12595 17636
31561 29178
19224 16725
62168 3819
34242 97295
19136 4746
23999 43879
16531 ...

output:

2
14322
29
31288
44
86287
97909
2487
356
21724
99944
2399
132
5428
95500
68144
16
20
87408
47
71962
6
29565
38966
94374
47
65210
79546
7
94340
98818
86021
7104
87791
12
99816
1010
5308
100000
1955
77970
99892
38926
100000
100000
99980
601
617
11
30821
99647
89978
1052
41
21123
5
90610
100000
3889
98...

result:

ok 100000 lines

Test #43:

score: 35
Accepted
time: 552ms
memory: 70068kb

input:

5 100000 20 100000
1342 1349
37640 37639
45877 45878
78332 78333
21484 21474
13801 13802
59570 59566
73931 73923
57631 57637
60889 60884
45602 45607
35865 35862
97617 97612
90212 90202
27887 27878
97274 97271
62494 62497
67320 67317
71745 71755
88665 88662
1544 1553
53066 53075
91559 91566
18097 180...

output:

37070
13884
96196
100000
100000
100000
65672
67310
51975
74849
21918
50480
100000
100000
73990
69136
100000
100000
100000
23751
100000
23888
30386
100000
100000
65774
100000
100000
69449
48250
100000
67132
53596
25327
63364
6915
73658
100000
100000
73912
100000
82194
15786
100000
100000
48929
92937
...

result:

ok 100000 lines

Test #44:

score: 35
Accepted
time: 531ms
memory: 69760kb

input:

5 100000 20 100000
59264 59258
87717 87713
22225 22233
41776 41783
38511 38503
89421 89418
59191 59188
77388 77394
99756 99755
96467 96468
4932 4923
22680 22684
59939 59942
3231 3237
32666 32675
45931 45941
68555 68563
60047 60040
47510 47509
71398 71400
39997 40002
4827 4823
60948 60951
75322 75312...

output:

100000
100000
53450
100000
100000
59130
100000
100000
100000
1143
100000
40600
100000
100000
100000
100000
69054
79660
100000
100000
100000
69564
100000
100000
51779
100000
100000
96458
71497
100000
100000
100000
66287
100000
100000
24105
45060
99864
43341
42672
73213
5611
100000
77610
100000
79621
...

result:

ok 100000 lines

Test #45:

score: 35
Accepted
time: 537ms
memory: 66572kb

input:

5 100000 20 100000
21461 21164
71167 70824
97255 97503
59623 59080
84738 85185
44114 44550
30324 30360
81441 81270
29850 30193
92272 92857
11808 12207
41553 41065
90015 90242
94350 94634
34000 33776
28572 28979
65660 65495
84076 83640
65227 65095
24103 23580
37412 37149
65839 66179
8898 9095
6723 62...

output:

73434
93433
47069
1759
66002
37763
22602
87270
0
100000
95679
17176
100000
98369
73678
96351
74314
2189
12154
100000
88797
56525
73048
19459
16041
13611
100000
75136
43
266
8861
97595
50759
11969
118
33131
32734
100000
71105
119
63382
72722
93256
3914
35262
98712
69440
59337
75790
89287
99917
72899
...

result:

ok 100000 lines

Test #46:

score: 35
Accepted
time: 560ms
memory: 65968kb

input:

5 100000 20 100000
30830 30987
29641 29277
91951 91752
86037 85940
79136 79653
4107 4641
35199 34681
41861 41656
5908 6540
29918 30138
27729 27139
68760 68440
3860 4152
81759 81999
49031 49170
4614 4599
75309 75715
44343 44166
32087 32011
28265 28802
73643 74140
23214 22910
20216 20640
46607 46343
1...

output:

886
100000
35274
235
246
64317
68101
92
64459
20893
77364
24261
36518
17495
45099
37369
54489
1259
79595
49213
40215
2091
54551
42
5314
51671
7430
98748
4678
995
51376
62526
82896
72479
11251
60740
82476
100000
93977
6366
97875
18485
96082
1156
54979
34
83294
96857
23365
90673
67027
18202
45715
8241...

result:

ok 100000 lines

Test #47:

score: 35
Accepted
time: 437ms
memory: 66144kb

input:

5 100000 5000 100000
89950 61865
92146 17194
23378 6354
19068 26442
3036 8450
97249 47870
1413 56517
70272 629
24274 15792
67638 99264
56427 24852
7607 11615
39 5824
74572 92104
63647 89870
24535 79943
25040 75115
34710 25843
11751 4477
37612 45293
8918 6453
1016 3107
40912 61802
44481 30453
16400 9...

output:

919
11
6339
34230
3764
666
86361
22
15959
94118
100000
94881
3038
86263
4190
81887
14967
934
85462
2438
190
94337
863
0
37324
25480
203
1167
3158
100000
4
45256
12
57
2
16
94833
6
6145
0
100000
6
100000
41144
31
26
55072
71967
3774
100000
91870
290
7
58470
25121
95000
785
80618
92873
58
93463
17441
...

result:

ok 100000 lines

Test #48:

score: 35
Accepted
time: 561ms
memory: 71004kb

input:

5 100000 5000 100000
85165 85169
86575 86565
25288 25291
49247 49246
85076 85073
33618 33608
62704 62695
18763 18755
75304 75313
3888 3889
92234 92244
12448 12440
94913 94911
18795 18805
98716 98722
62402 62400
12488 12487
63455 63454
13056 13064
29380 29382
85700 85703
71729 71725
59986 59996
69405...

output:

48038
25974
100000
100000
100000
21400
100000
100000
9263
62996
65410
38758
90367
75490
2834
100000
100000
100000
27629
9506
100000
45965
55865
100000
45511
68133
53328
100000
88324
2993
100000
100000
54622
13650
22464
100000
100000
38893
28099
100000
26722
28069
100000
91626
100000
100000
100000
10...

result:

ok 100000 lines

Test #49:

score: 35
Accepted
time: 566ms
memory: 69240kb

input:

5 100000 5000 100000
85690 85695
4099 4103
92471 92481
70406 70399
96641 96636
49712 49719
35442 35443
41413 41404
87428 87426
34247 34253
34758 34757
37596 37605
21128 21135
21900 21910
34748 34757
40288 40283
18622 18632
79848 79841
67275 67271
40991 40988
60576 60577
20748 20754
94379 94376
87474...

output:

100000
100000
100000
100000
74331
100000
879
21052
100000
100000
100000
100000
77185
4768
35808
100000
91727
88541
86660
100000
100000
100000
100000
32313
100000
100000
93215
100000
100000
43928
65754
76966
16
77184
100000
85011
100000
100000
67970
100000
100000
57699
7229
75837
84395
100000
94705
1...

result:

ok 100000 lines

Test #50:

score: 35
Accepted
time: 531ms
memory: 66516kb

input:

5 100000 5000 100000
35256 35062
93687 93723
21373 21942
31950 32049
13404 13173
71077 71691
94160 93713
70966 71112
84946 84304
6152 6452
85538 86080
92237 92673
80980 81182
35870 36287
85682 85693
35402 35771
98713 98160
19146 18543
856 955
91720 91203
34217 33691
80360 80266
56201 56335
62955 631...

output:

100000
19309
56810
84169
23855
26571
34507
65727
62312
12073
30622
41517
100000
72524
9153
11295
6928
2211
56676
86146
37265
1906
24328
24608
43825
59628
100000
62164
45377
100000
5383
65890
61417
5068
89535
100000
6006
22
85407
85
61728
1514
23446
100000
10853
8925
1915
26819
0
18453
2231
56466
711...

result:

ok 100000 lines

Test #51:

score: 35
Accepted
time: 560ms
memory: 65168kb

input:

5 100000 5000 100000
40326 40237
82510 82921
3255 2919
57214 57457
15713 15510
3712 4285
10172 10450
19602 19723
86063 85621
23568 23876
39998 40130
72647 72167
46400 46779
68591 68602
31093 31614
97900 97353
14724 15335
48298 48411
13860 13770
53707 53150
80521 79948
78513 78555
55703 56139
45206 4...

output:

59562
40154
59325
7116
39661
956
40297
39817
7209
14251
25914
83621
18438
52509
57633
94596
67827
85680
72528
100000
12
8261
60080
70680
66441
838
75417
79221
566
10663
100000
94881
100000
8130
53190
68767
32773
90395
77237
17629
81774
36360
490
28337
66155
19277
85371
21252
93321
37984
41715
54912
...

result:

ok 100000 lines

Subtask #6:

score: 5
Accepted

Dependency #5:

100%
Accepted

Test #52:

score: 5
Accepted
time: 744ms
memory: 72120kb

input:

6 100000 3000 300000
24522 9089
42285 11117
6455 985
637 20347
21686 21193
66625 15902
81546 83181
224 175
11887 38177
91158 20556
76059 84399
2967 73086
18508 66441
19875 24675
12012 11534
82425 24704
29358 48319
31804 72664
13770 4137
43278 35101
2927 44385
11550 7417
78317 965
6969 6379
63283 796...

output:

430
241763
242666
297000
624
300000
34054
117562
38217
91342
20
300000
296901
258740
3
296581
273069
295888
2467
26483
291840
13738
21177
57
37595
300000
300000
207733
163939
296710
15
0
5728
188423
296727
295888
300000
296581
50884
349
300000
300000
19
572
207733
80
268930
300000
0
47790
295755
129...

result:

ok 300000 lines

Test #53:

score: 5
Accepted
time: 941ms
memory: 76656kb

input:

6 100000 3000 300000
85797 85796
72149 72142
21553 21554
93667 93663
10966 10973
60095 60098
43451 43460
8205 8210
19140 19135
29375 29365
73716 73711
56106 56111
63322 63332
41804 41810
30436 30432
38898 38905
29084 29091
73118 73127
67108 67104
88436 88440
19500 19495
49759 49754
61601 61607
36454...

output:

184106
82774
300000
272171
300000
300000
300000
256550
300000
300000
62309
204503
239874
300000
300000
252895
300000
236875
170780
173974
300000
300000
285297
300000
300000
300000
300000
276192
250065
300000
81406
300000
300000
300000
300000
192237
300000
63136
155126
264221
247459
142062
300000
300...

result:

ok 300000 lines

Test #54:

score: 5
Accepted
time: 870ms
memory: 71388kb

input:

6 100000 3000 300000
43156 43362
74429 73786
55797 55918
55626 55398
96268 96293
55284 55026
6571 6808
69286 68957
63793 63717
49324 49045
26719 27250
37255 36651
73268 73037
44786 44456
18080 18690
94876 95505
80729 80294
81889 82159
84578 83933
89571 89065
81102 80552
59597 59382
51589 51793
28357...

output:

14726
156406
209347
300000
50463
179421
37590
134550
99811
178888
133392
272747
124846
5016
14092
151830
278650
43162
9179
127988
69683
95590
10172
28863
243292
2315
2401
5992
115173
186237
12481
95002
29887
300000
131179
300000
192342
1505
0
26947
241
152815
246561
1264
218534
80221
249966
264642
3...

result:

ok 300000 lines

Test #55:

score: 5
Accepted
time: 724ms
memory: 72528kb

input:

6 100000 100 300000
56178 61223
19550 15322
21077 12277
2093 53
1641 11554
7649 61213
6431 2790
12351 34894
78933 72747
2113 5837
2384 433
70693 60724
11269 56788
71704 80110
36109 76638
39872 41293
37059 67110
33593 33422
20626 42747
30541 43987
59668 56664
37044 96199
93422 54898
75751 66473
17731...

output:

300000
85108
95701
282703
140745
75
2819
0
300000
133667
0
1955
291
5738
283049
298363
0
6
173918
32549
7
21
255
0
6704
300000
299748
300000
300000
8106
300000
364
262400
13305
300000
2824
300000
1792
6
68849
290727
300000
69
111986
291661
10
137
249630
0
283049
298818
232153
0
204402
14099
0
33
783...

result:

ok 300000 lines

Test #56:

score: 5
Accepted
time: 909ms
memory: 76508kb

input:

6 100000 100 300000
33374 33367
388 380
36644 36652
11055 11057
43638 43632
43932 43926
17054 17055
59769 59765
8027 8021
1675 1683
85648 85644
98844 98852
91914 91919
93235 93236
39042 39052
84484 84477
82473 82479
95522 95526
48696 48706
49376 49367
34407 34410
29868 29867
30512 30509
22691 22681
...

output:

300000
207939
300000
136487
300000
300000
125407
300000
300000
300000
300000
197530
300000
300000
300000
300000
300000
45707
300000
208402
300000
300000
300000
300000
295506
300000
5259
300000
300000
300000
290685
300000
214834
300000
300000
191928
48417
215556
300000
300000
34772
300000
300000
1249...

result:

ok 300000 lines

Test #57:

score: 5
Accepted
time: 936ms
memory: 72536kb

input:

6 100000 100 300000
37965 38216
46332 46065
42847 42641
29308 28996
54716 54278
94221 94273
44066 43897
35776 35547
57531 57321
94121 94345
68624 68696
11632 11013
87323 87836
65617 65731
97906 98339
74072 74161
77580 77275
55148 54555
4074 3440
76377 75787
14882 14680
40712 41031
30530 30057
75589 ...

output:

2755
131795
131732
249003
117832
181265
300000
20968
65271
299572
274388
422
211847
3072
2141
238110
722
37849
52082
179539
47110
300000
68994
143877
273738
300000
113953
300000
25577
300000
300000
22958
184467
22503
54772
173712
300000
2235
17085
200620
28312
7922
26942
1241
139053
153226
552
30000...

result:

ok 300000 lines

Test #58:

score: 5
Accepted
time: 409ms
memory: 81280kb

input:

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

output:

109834
270000
12639
176354
5432
47124
251816
109834
1977
222319
285000
285000
25605
270000
5548
636
74498
285000
42352
270000
197523
84910
236955
285000
16114
285000
10905
285000
285000
176354
55357
270000
251816
251816
5612
270000
5584
11060
157024
109834
10596
236955
98934
71838
207589
285000
5234...

result:

ok 300000 lines

Test #59:

score: 5
Accepted
time: 406ms
memory: 83768kb

input:

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

output:

5718
254342
280000
290000
290000
63982
280000
290000
28723
22767
30982
153154
27730
290000
254342
280000
290000
56018
125229
112894
135183
30966
290000
41797
290000
152163
217279
290000
14657
290000
17165
26073
13916
8871
280000
152163
17288
224707
52602
290000
3306
224772
54018
290000
280000
13916
...

result:

ok 300000 lines

Test #60:

score: 5
Accepted
time: 438ms
memory: 79740kb

input:

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

output:

26042
270000
6910
4827
100458
5033
117401
5811
240000
270000
230130
58312
43038
0
10777
43038
240000
20349
240000
270000
270000
39387
270000
678
117401
2219
235190
86394
8807
9661
270000
9796
235190
270000
5779
30333
44256
5631
230130
235190
35813
230130
235190
270000
270000
43038
235190
28569
18315...

result:

ok 300000 lines