QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279611#6388. Networkdeadeye0100 ✓187ms48748kbC++202.8kb2023-12-08 22:16:512023-12-08 22:16:51

Judging History

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

  • [2023-12-08 22:16:51]
  • 评测
  • 测评结果:100
  • 用时:187ms
  • 内存:48748kb
  • [2023-12-08 22:16:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
#define ar array
#define pb push_back
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
typedef vector<int> vi;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 200010, LOG = 18;
int n, m, ans;
vector<int> g[N], nodes;
vector<ar<int,3>> big;

int cnt = 1;
int pre[N], post[N], dep[N];
int up[N][LOG];
void dfs(int x, int p) {
    pre[x] = cnt++;
    up[x][0] = p;
    if (p != -1) dep[x] = dep[p] + 1;
    for (int i = 1; i < LOG; ++i) {
        if (up[x][i - 1] == -1) continue;
        up[x][i] = up[up[x][i - 1]][i - 1];
    }
    for (int i: g[x]) {
        if (i == p) continue;
        dfs(i, x);
    }
    post[x] = cnt - 1;
}

int jump(int x, int k) {
    for (int i = 0; i < LOG; ++i) {
        if (x == -1) return -1;
        if (k & (1 << i)) x = up[x][i];
    }
    return x;
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    a = jump(a, dep[a] - dep[b]); 
    if (a == b) return a;
    for (int i = LOG - 1; i >= 0; --i) {
        if (up[a][i] == -1 || up[b][i] == -1) continue;
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

int fw[N], fw2[N];
void update(int x, int y, int v) { 
    for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
int sum(int x) {
    int res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
int query(int x, int y) {
    return sum(y) - sum(x - 1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    memset(up, -1, sizeof up);
    dfs(1, -1);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        big.pb({lca(u, v), u, v});
    }
    sort(big.begin(), big.end(), [&](ar<int,3> x, ar<int,3> y) {
        return dep[x[0]] > dep[y[0]];
    });
    for (auto i: big) {
        int u = i[1], v = i[2];
        if (query(pre[u], pre[u]) || query(pre[v], pre[v])) continue;
        update(pre[i[0]], post[i[0]], 1);
        ++ans;
        nodes.pb(i[0]);
    }
    cout << ans << '\n';
    for (auto i: nodes) cout << i << ' ';
    return 0;
}

詳細信息

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 88ms
memory: 48748kb

input:

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

output:

200000
200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 199959...

result:

ok correct plan

Test #2:

score: 0
Accepted
time: 62ms
memory: 34656kb

input:

192791 177013
15163 96594
16414 102268
89243 170228
57950 132600
162574 32273
2947 78186
41636 62390
73315 15163
159645 21314
185962 122448
75023 149485
145294 145941
154151 174468
11494 16133
14507 183387
92177 141072
71628 187859
123587 177507
55726 185406
170316 48341
28477 167274
76200 94096
717...

output:

113
186804 189439 192014 189298 174817 192139 183355 176078 178052 181537 185278 177480 175396 185143 182261 181168 173907 170066 174190 167978 163887 167132 165535 160828 156447 162182 158538 157539 159731 157805 186400 188963 191921 184702 186904 177820 183845 186889 189994 186027 192732 185422 19...

result:

ok correct plan

Test #3:

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

input:

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

output:

122449
193083 193082 193079 193078 193075 193074 193073 193072 193071 193067 193066 193065 193064 193063 193060 193059 193057 193053 193052 193051 193048 193047 193043 193042 193040 193038 193037 193036 193035 193034 193033 193032 193026 193025 193024 193023 193022 193020 193018 193017 193016 193014...

result:

ok correct plan

Test #4:

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

input:

1 15
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

output:

1
1 

result:

ok correct plan

Test #5:

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

input:

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

output:

7
11 9 8 7 13 14 1 

result:

ok correct plan

Test #6:

score: 0
Accepted
time: 6ms
memory: 23612kb

input:

2000 2000
646 1544
259 1127
1827 903
859 292
1520 1908
478 1986
1471 1556
1829 894
32 1676
876 1610
234 1082
36 1554
408 1056
1910 931
290 1091
1246 1491
280 1923
1244 1084
843 1940
227 756
961 733
856 255
1496 1750
1951 961
758 816
319 1413
302 1932
122 11
1853 53
113 1600
1391 1654
1995 1680
1626 ...

output:

1251
209 855 375 1472 1506 1214 811 1764 1821 1739 892 1385 1566 216 987 824 1912 245 1870 1362 1030 537 314 1841 1370 67 1049 1970 1887 1915 531 149 558 838 996 247 1181 101 274 510 1201 1763 1932 4 1217 307 97 577 522 1208 1485 1460 1753 1576 219 1913 1508 1023 1163 1256 504 958 1699 61 45 265 102...

result:

ok correct plan

Test #7:

score: 0
Accepted
time: 116ms
memory: 35348kb

input:

198912 186079
95780 144147
156043 6576
73725 177413
193666 6531
3185 35106
50448 92669
57454 69007
125547 119658
48130 110361
134981 69883
112070 85977
55781 101462
142588 148493
22305 45089
54391 189769
82051 53939
76255 10560
143560 197809
117454 69061
134035 101491
23080 88239
132686 178401
59762...

output:

120929
110908 76283 170538 132048 137648 109818 143084 55144 67638 82955 113576 16782 47359 102610 19113 170735 48845 85093 173936 52635 61511 159881 64054 186205 155937 109428 155296 35587 113228 2837 121049 82948 15882 195396 96855 102852 135498 190977 8294 158025 47568 116351 29323 185103 129342 ...

result:

ok correct plan

Subtask #2:

score: 17
Accepted

Test #8:

score: 17
Accepted
time: 58ms
memory: 47752kb

input:

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

output:

100001
200000 199998 199996 199994 199992 199990 199988 199986 199984 199982 199980 199978 199976 199974 199972 199970 199968 199966 199964 199962 199960 199958 199956 199954 199952 199950 199948 199946 199944 199942 199940 199938 199936 199934 199932 199930 199928 199926 199924 199922 199920 199918...

result:

ok correct plan

Test #9:

score: 0
Accepted
time: 145ms
memory: 47128kb

input:

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

output:

502
199736 199187 199019 198812 198385 197865 197488 197434 196996 196548 195822 195297 194817 194425 194258 193854 193520 192880 192565 191928 191422 191006 190810 190632 190353 190170 189718 189184 188540 188102 187821 187626 187037 186379 186023 185915 185453 184741 184641 184033 183782 183605 18...

result:

ok correct plan

Test #10:

score: 0
Accepted
time: 105ms
memory: 47524kb

input:

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

output:

5417
199976 199959 199936 199923 199911 199897 199886 199873 199862 199850 199835 199828 199817 199811 199802 199788 199776 199769 199746 199732 199719 199711 199702 199683 199682 199667 199648 199629 199613 199598 199582 199572 199564 199549 199527 199522 199517 199515 199501 199486 199478 199463 1...

result:

ok correct plan

Test #11:

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

input:

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

output:

45
1995 1959 1903 1861 1830 1809 1772 1709 1619 1593 1569 1538 1509 1463 1397 1346 1290 1206 1152 1064 1035 1020 995 958 933 859 803 749 679 654 636 584 552 477 401 349 284 188 180 159 152 98 71 47 5 

result:

ok correct plan

Test #12:

score: 0
Accepted
time: 87ms
memory: 47428kb

input:

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

output:

1
14123 

result:

ok correct plan

Test #13:

score: 0
Accepted
time: 136ms
memory: 46260kb

input:

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

output:

4
145045 107588 78878 34415 

result:

ok correct plan

Test #14:

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

input:

5 2
1 2
2 3
3 4
4 5
1 2
1 2

output:

1
1 

result:

ok correct plan

Subtask #3:

score: 14
Accepted

Test #15:

score: 14
Accepted
time: 3ms
memory: 24916kb

input:

5 15
5 4
3 4
5 1
5 2
4 4
1 4
2 2
4 2
5 2
1 3
1 2
3 1
3 5
2 4
2 2
1 4
3 4
5 4
3 4

output:

2
4 2 

result:

ok correct plan

Test #16:

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

input:

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

output:

7
6 5 9 10 13 12 1 

result:

ok correct plan

Test #17:

score: 0
Accepted
time: 5ms
memory: 24268kb

input:

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

output:

3
5 7 9 

result:

ok correct plan

Subtask #4:

score: 29
Accepted

Dependency #3:

100%
Accepted

Test #18:

score: 29
Accepted
time: 3ms
memory: 25480kb

input:

40 2000
24 18
24 23
38 26
26 13
4 8
9 35
7 17
23 22
25 40
34 28
6 3
32 16
17 16
27 33
3 40
22 16
2 23
31 18
40 35
11 12
29 16
30 12
35 12
18 26
15 6
28 1
26 36
3 5
23 19
33 10
33 23
39 28
22 8
19 21
37 19
23 12
20 14
28 27
14 28
16 24
15 1
6 16
34 30
16 24
2 32
8 12
35 33
37 25
37 28
30 32
36 35
36 ...

output:

29
15 5 6 36 38 32 40 4 17 26 9 16 11 18 35 37 21 30 19 24 22 2 23 10 33 14 27 28 1 

result:

ok correct plan

Test #19:

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

input:

2000 40
324 734
227 1309
485 1789
300 1206
1035 1390
1789 62
576 629
1997 1787
668 848
1075 1768
1920 1601
876 1223
619 309
557 870
1381 394
1202 1857
786 1851
1614 938
1142 1779
489 1652
927 1035
800 1424
494 176
1643 576
1130 1970
36 1148
1076 656
1229 284
990 427
1229 1774
422 602
1467 1528
408 1...

output:

6
1923 1761 1570 909 1911 104 

result:

ok correct plan

Test #20:

score: 0
Accepted
time: 7ms
memory: 24336kb

input:

1999 1998
921 63
1320 19
754 1091
454 1602
840 679
1713 852
1959 984
250 1751
1407 949
1949 208
1884 1560
703 636
1628 582
1736 1810
1998 955
1041 840
1591 1776
1032 1877
1319 1178
360 583
691 129
1510 1799
440 1807
307 939
976 880
1326 81
1386 1782
69 477
1234 1896
999 322
1136 931
1507 1780
1916 2...

output:

378
1819 1243 567 561 651 1902 1944 1363 1561 1782 1990 1703 344 402 1934 372 430 768 1124 1256 1686 1446 1289 1162 1828 312 1635 856 712 117 571 1370 1013 1915 1810 432 152 1317 608 1343 79 382 1073 1247 951 992 249 1168 1080 443 1564 1267 1727 1135 1169 559 412 225 1977 389 107 623 1062 1946 1502 ...

result:

ok correct plan

Test #21:

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

input:

2000 2000
1242 38
3 1172
1653 105
616 917
721 704
563 53
1643 1708
1743 1969
638 763
1603 1855
624 55
616 707
471 1725
233 838
691 1691
82 1799
902 1396
1741 1071
870 1979
100 1113
883 1612
738 533
372 1132
1467 1259
1953 994
1286 1980
156 796
1319 976
1481 213
506 1748
1908 7
1440 1655
927 498
1254...

output:

29
1864 1492 1156 595 1378 948 1481 1531 1529 1220 1822 1229 984 1104 1418 1431 1197 1564 1866 1114 723 1763 1252 583 1565 1203 1408 935 1106 

result:

ok correct plan

Test #22:

score: 0
Accepted
time: 3ms
memory: 23740kb

input:

2000 2000
1100 1952
822 756
1211 1245
1457 33
554 224
894 1548
1909 1991
365 1489
428 1489
1952 1746
1289 1280
206 1503
1109 375
881 1205
1812 769
431 1597
127 873
242 1570
1952 1735
931 1356
245 1969
1345 873
1138 57
1994 122
1628 1243
1503 1414
743 756
756 431
756 1447
1883 1993
1217 1952
1969 105...

output:

17
455 873 1871 1152 1952 1489 1113 520 1503 1969 224 1280 57 637 1343 1941 756 

result:

ok correct plan

Test #23:

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

input:

1922 1993
913 460
1350 1848
1551 225
1692 301
1415 885
1751 254
1257 425
323 475
665 783
612 763
272 1016
747 480
715 1550
321 1609
1111 1669
1003 1413
881 1742
331 1829
519 1087
1080 668
900 1846
1386 1760
1352 183
1148 481
1156 1683
662 1861
188 716
1643 1425
1433 1029
1834 1195
1070 254
1590 454
...

output:

40
1018 1812 1664 1122 639 650 1395 1345 1583 850 1700 446 1902 928 511 695 319 1602 301 1825 297 1016 937 1652 300 1109 357 598 157 1718 1154 288 1912 1739 523 810 65 1570 507 1441 

result:

ok correct plan

Test #24:

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

input:

150 2000
119 133
136 119
86 119
119 34
119 100
119 13
76 119
119 65
119 71
119 130
119 66
143 119
119 150
119 115
119 9
119 25
64 119
119 73
74 119
40 119
119 82
119 35
119 110
111 119
119 132
119 20
50 119
87 119
119 120
119 6
7 119
119 90
92 119
126 119
32 119
119 29
119 144
96 119
119 42
8 119
11...

output:

12
91 73 15 65 42 141 131 28 54 118 76 119 

result:

ok correct plan

Subtask #5:

score: 36
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #25:

score: 36
Accepted
time: 33ms
memory: 26656kb

input:

1000 200000
962 786
10 602
689 122
331 609
456 224
682 555
258 809
340 387
460 90
850 387
305 977
139 820
73 439
783 713
855 235
302 3
271 474
468 946
93 308
819 976
69 548
790 83
25 642
506 841
39 853
665 520
186 952
282 704
192 544
206 756
903 458
207 461
222 293
305 620
167 473
218 838
436 963
33...

output:

365
490 818 530 391 636 245 602 504 518 278 235 921 219 465 917 172 199 186 915 815 332 963 402 552 128 752 507 585 251 435 162 464 767 195 671 942 283 410 255 41 371 372 836 65 67 447 17 365 760 203 232 599 392 36 120 346 827 158 551 901 974 173 122 22 803 742 929 287 983 592 736 845 934 980 78 756...

result:

ok correct plan

Test #26:

score: 0
Accepted
time: 57ms
memory: 31944kb

input:

200000 1000
95107 88168
164771 85445
66359 162412
163788 180604
34366 91353
106881 49515
160504 82649
164411 27137
8466 118113
76696 110444
183716 55642
183361 57033
35294 82872
72862 71258
142773 21106
143580 42596
110137 165652
146176 170264
198469 142707
69183 43753
38091 114103
184519 46414
3837...

output:

35
97190 140609 138039 162238 118099 54009 108306 123748 55215 128781 24248 39248 94292 157460 47353 87736 136181 15485 85967 46465 113563 118112 30322 106804 83571 185421 185863 93930 164459 159029 105664 19204 6870 8208 1 

result:

ok correct plan

Test #27:

score: 0
Accepted
time: 137ms
memory: 34136kb

input:

185187 190124
129481 181690
140662 95760
169227 45363
139452 85447
33367 61989
11211 71033
184146 43438
177997 67240
112457 114889
169331 31429
157559 26171
30228 104581
72925 124203
60734 119134
182866 88147
159343 61451
142062 70863
160999 80006
132410 61922
184613 135766
88844 13399
28172 171484
...

output:

368
113156 137926 4250 129730 177762 25525 87481 123619 171602 89933 146047 7034 67544 139459 139718 103293 21221 75776 156293 38617 158549 109288 109036 7121 67266 98979 111025 67134 56427 180383 42285 44707 86936 18408 157315 153258 5288 19858 64178 111332 137131 133251 146128 70762 176417 38291 6...

result:

ok correct plan

Test #28:

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

input:

199023 194992
112150 381
61419 62872
61493 109624
197795 111364
137979 61211
1807 100136
98752 183589
27951 9284
5836 93144
78987 24773
17566 123497
44908 183698
119459 186104
145308 130621
157247 189676
18511 169097
7633 180862
87954 29481
155086 118436
61203 62285
53853 31684
162988 46237
153023 1...

output:

15303
12124 148614 10258 61188 103248 98601 132291 110781 81640 149672 131186 133620 117498 167305 59738 171396 7732 22788 108223 60775 131846 48579 1188 87357 105735 180671 69151 26614 51308 71785 193970 43492 35513 96751 2797 86862 157461 139757 17239 29867 73213 132767 116990 4969 165065 181943 2...

result:

ok correct plan

Test #29:

score: 0
Accepted
time: 163ms
memory: 34800kb

input:

199675 197898
16067 23538
35080 107246
156465 86388
58637 139661
18908 67140
157193 188391
177753 80905
33730 68936
14860 156486
182042 62689
78274 133213
65374 179074
159979 180325
1191 11882
177049 5310
142145 148996
180278 105063
164908 46889
35330 25704
167829 77893
107073 87455
118234 84839
122...

output:

485
67405 150558 22474 198040 144982 55985 104275 74265 190355 15932 51517 38261 156515 145562 92399 75679 3448 62828 69378 9143 107273 49171 70013 10554 127570 74391 51407 110539 149570 13534 161563 61812 170955 183542 110407 33601 5345 186774 198909 96141 195999 100465 160588 194964 21425 154362 2...

result:

ok correct plan

Test #30:

score: 0
Accepted
time: 84ms
memory: 33852kb

input:

188144 189189
113457 126804
172368 902
135979 124925
52117 30447
50855 151736
10826 79905
112635 160398
36405 76006
115641 49725
118723 160596
36598 64055
56276 6591
106106 50501
55734 13740
84294 46053
2132 106130
38498 127898
47536 23430
109961 129969
111107 28576
142369 142132
148458 108051
14537...

output:

109
149615 149128 168258 158415 107932 131930 112016 133280 131234 167126 136520 170197 161935 147908 147561 142013 151097 128146 164578 187708 133018 177234 136234 133668 165890 170536 122591 128191 120114 139642 157520 128778 163210 127610 131588 152823 154893 136096 143574 142095 168388 150277 11...

result:

ok correct plan

Test #31:

score: 0
Accepted
time: 108ms
memory: 35388kb

input:

197567 197283
76986 5176
162491 82631
153709 153234
122448 119015
46542 134867
144078 36712
87847 56340
55550 152283
131639 157934
69114 80854
95441 107667
87709 108324
194073 78052
23351 173199
92762 23785
107493 145155
36686 114909
95441 26463
23558 418
24192 95441
188076 182221
122910 196908
8147...

output:

181
177934 137299 170053 91311 180043 74184 57554 132475 70358 27385 195062 164883 69031 73951 140895 3619 116432 180181 84326 65697 195645 27030 115507 34396 43773 144078 67535 82628 92044 108324 150394 146144 189991 51637 35737 48640 16062 87061 176461 29222 90785 185187 37082 418 133175 76438 291...

result:

ok correct plan

Test #32:

score: 0
Accepted
time: 173ms
memory: 35156kb

input:

199999 199998
57299 111055
31703 48204
138530 64729
4600 166389
182536 187355
100197 82429
35502 24171
35688 91780
44623 157178
7241 184089
140355 193065
13714 166126
11578 184978
12311 58219
21287 118071
166322 177326
88842 196118
139280 79683
145174 41137
32309 4491
145206 58270
132044 47673
34482...

output:

499
152649 161267 82106 123558 187304 25778 44914 68411 141206 59538 105110 55929 16161 68343 15298 126331 109281 123961 175540 45022 61318 192611 123347 193481 61130 80493 47915 86749 114175 33191 75754 44971 25726 151372 116145 99719 69635 149261 173331 108787 27926 159848 45977 58368 111862 65204...

result:

ok correct plan

Test #33:

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

input:

200000 200000
135271 36583
109466 135271
40256 135271
135271 111522
141759 135271
188471 135271
133818 135271
135271 88349
115520 135271
96459 135271
117693 135271
135271 99209
135271 75826
135271 167880
135271 99672
135271 176594
183481 135271
77190 135271
197698 135271
193882 135271
135271 154656
...

output:

1
135271 

result:

ok correct plan

Test #34:

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

input:

200000 200000
76496 153200
107795 113185
159406 16131
127262 90537
43113 182602
170954 168070
83387 3383
15385 116831
191157 42268
142379 72960
156347 53592
163269 159122
29345 40574
61150 40382
65207 22984
94675 160869
26519 154814
10651 22764
60852 114858
191065 166952
47089 70874
128594 115795
18...

output:

492
193881 119543 157475 68948 70481 3193 59142 43539 157449 90389 58438 5639 56151 169174 37986 187277 145196 156402 16192 131331 121179 175744 187516 130970 114843 136046 23167 124552 40481 102142 36845 55114 53224 73215 96651 178112 80186 110869 164050 91039 167456 75302 83459 2603 168879 112649 ...

result:

ok correct plan

Test #35:

score: 0
Accepted
time: 122ms
memory: 34664kb

input:

200000 200000
14980 136780
44323 79762
56355 132044
158375 82833
189773 80348
14529 178342
62749 130697
61919 36105
186627 167479
136960 128736
73870 123049
1448 25238
46365 167002
123272 150814
62234 145472
9864 176429
127389 42159
41705 13715
112747 158444
136311 138613
168668 49610
43693 143003
7...

output:

461
73304 27785 50250 101921 84642 148344 105803 180121 63568 69628 140048 28171 150365 47488 43589 99358 22384 33372 28208 148698 128378 77836 61919 14895 96724 187581 7632 197584 58110 128656 110399 53666 91627 48716 38569 161288 120577 112029 13689 32037 116634 115299 175559 64897 58172 179669 15...

result:

ok correct plan

Test #36:

score: 0
Accepted
time: 187ms
memory: 42384kb

input:

200000 200000
91610 157149
169751 144801
164986 81171
89525 134455
30949 57500
184578 30443
84434 27008
89793 156988
199474 182061
33191 99697
86720 164130
83125 1073
42970 184483
1335 1032
154225 25386
130159 123083
129354 99811
50757 82711
90620 89351
53688 31659
42135 146681
29266 7620
31387 5316...

output:

5
60638 76505 145436 7717 1 

result:

ok correct plan

Test #37:

score: 0
Accepted
time: 139ms
memory: 45088kb

input:

199999 199999
1 2
2 3
3 4
3 184691
3 187429
4 5
5 6
6 7
7 8
8 9
8 190964
9 10
10 11
11 12
12 13
13 14
14 15
15 16
15 169232
15 175253
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
23 192679
24 25
25 26
25 163741
26 27
27 28
28 29
29 30
29 170209
30 31
31 32
31 178883
32 33
33 34
34 35
35 36
36 37
...

output:

220
159205 158356 157683 156569 155864 155515 155164 154318 153961 152929 151898 151159 150416 149744 149023 148245 147425 146740 146155 146077 145591 145039 143743 142141 141497 141418 140996 139764 139561 138744 137363 137185 136602 135967 135643 134975 134094 133808 133733 133099 132312 131357 13...

result:

ok correct plan

Test #38:

score: 0
Accepted
time: 134ms
memory: 46136kb

input:

200000 200000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
9 191957
10 11
11 12
12 13
13 14
14 15
15 16
15 195223
15 196855
16 17
17 18
18 19
19 20
20 21
20 195602
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
...

output:

100
188701 186530 184449 182162 180927 179792 179142 178777 177524 176036 174573 174474 170959 169568 168677 167204 166872 162624 161775 161018 159676 159380 156191 153980 151266 147262 144369 141276 140583 139495 136532 135579 131724 128667 126164 123691 121661 120165 116941 116191 114242 112421 11...

result:

ok correct plan

Extra Test:

score: 0
Extra Test Passed