QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720025#9607. 熟练yyyyxh100 ✓1116ms258708kbC++204.1kb2024-11-07 10:19:442024-11-07 10:19:45

Judging History

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

  • [2024-11-07 10:19:45]
  • 评测
  • 测评结果：100
  • 用时：1116ms
  • 内存：258708kb
查看
  • [2024-11-07 10:19:44]
  • 提交

answer

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <functional>
#include <queue>
using namespace std;
int read() {
    char c = getchar();
    int x = 0;
    while (c < 48 or c > 57)
        c = getchar();
    do
        x = x * 10 + (c ^ 48), c = getchar();
    while (c >= 48 and c <= 57);
    return x;
}
const int N = 500003;
typedef pair<int, int> pii;
int n, m, cur;
int hd[N], ver[N << 1], nxt[N << 1], tot;
void add(int u, int v) {
    nxt[++tot] = hd[u], hd[u] = tot, ver[tot] = v;
}
__gnu_pbds::gp_hash_table<int, int> mp[N];
priority_queue<int, vector<int>, greater<int>> pq[N];
vector<pii> vec[N];
int eu[N], ev[N], ew[N];
int p[N], col[N], now[N];
int sz[N], tp[N], ft[N], sn[N], d[N];
int lca(int u, int v) {
    while (tp[u] ^ tp[v]) {
        if (d[tp[u]] < d[tp[v]])
            swap(u, v);
        u = ft[tp[u]];
    }
    if (d[u] < d[v])
        return u;
    else
        return v;
}
void dfs(int u, int fa) {
    sz[u] = 1, ft[u] = fa, sn[u] = 0;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = ver[i];
        if (v == fa)
            continue;
        d[v] = d[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[sn[u]])
            sn[u] = v;
    }
}
void split(int u, int tops) {
    tp[u] = tops;
    if (sn[u])
        split(sn[u], tops);
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = ver[i];
        if (v == ft[u] or v == sn[u])
            continue;
        split(v, v);
    }
}
void upd(int p, int v) {
    while (p and d[p] >= cur) {
        ++mp[tp[p]][v];
        vec[d[p]].emplace_back(tp[p], v);
        p = ft[tp[p]];
    }
}
void solve() {
    n = read();
    m = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    d[1] = 0;
    dfs(1, 0);
    split(1, 1);
    for (int i = 1; i <= m; ++i) {
        p[i] = i;
        eu[i] = read(), ev[i] = read();
        ew[i] = lca(eu[i], ev[i]);
    }
    sort(p + 1, p + m + 1, [](int x, int y) {
        if (d[ew[x]] != d[ew[y]])
            return d[ew[x]] < d[ew[y]];
        else
            return ew[x] < ew[y];
    });
    cur = 0;
    for (int i = 1; i <= m; ++i) {
        int x = p[i];
        while (cur < d[ew[x]]) {
            for (auto [t, v] : vec[cur])
                if (!--mp[t][v] and v <= now[t])
                    pq[t].emplace(v);
            ++cur;
        }
        int o = tp[ew[x]];
        assert(o <= n);
        while (true) {
            if (pq[o].empty()) {
                auto it = mp[o].find(++now[o]);
                if (it != mp[o].end() and it->second)
                    continue;
                pq[o].emplace(col[x] = now[o]);
                break;
            } else {
                bool fl = 0;
                while (!pq[o].empty()) {
                    int v = pq[o].top();
                    auto it = mp[o].find(v);
                    if (it != mp[o].end() and it->second) {
                        pq[o].pop();
                        continue;
                    }
                    col[x] = v, fl = 1;
                    break;
                }
                if (fl)
                    break;
            }
        }
        upd(eu[x], col[x]);
        upd(ev[x], col[x]);
    }
    printf("%d\n", *max_element(col + 1, col + m + 1));
    for (int i = 1; i <= m; ++i)
        printf("%d ", col[i]), col[i] = 0;
    putchar('\n');
    while (tot)
        ver[tot] = nxt[tot] = 0, --tot;
    for (int i = 0; i <= n; ++i) {
        tp[i] = sn[i] = ft[i] = d[i] = hd[i] = now[i] = sz[i] = 0;
        mp[i].clear();
        vec[i].clear();
        while (!pq[i].empty())
            pq[i].pop();
    }
    for (int i = 0; i <= n; ++i) {
        mp[i].clear();
        vec[i].clear();
        while (!pq[i].empty())
            pq[i].pop();
    }
}
int main() {
    read();
    int tc = read();
    while (tc--)
        solve();
    return 0;
}
源文件, 语言: C++20

详细

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 94ms
memory: 146516kb

input:

1
100000
1 2
1 1
1 1
3 5
1 2
2 3
2 1
2 3
1 1
1 1
3 3
1 3
1 1
1 1
1 1
4 4
1 2
2 3
3 4
3 3
2 1
3 3
4 2
5 3
1 2
1 3
1 4
2 5
1 1
3 3
3 1
1 5
1 1
1 1
1 1
1 1
1 1
2 5
1 2
2 1
1 2
1 2
1 2
1 2
2 2
1 2
2 2
2 2
4 2
1 2
1 3
1 4
4 4
2 3
2 3
1 2
1 2
1 1
1 1
1 4
1 1
1 1
1 1
1 1
5 3
1 2
2 3
3 4
4 5
3 4
4 5
5 2
2 1...

output:

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

result:

ok ok

Subtask #2:

score: 14
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 14
Accepted
time: 75ms
memory: 155348kb

input:

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

output:

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

result:

ok ok

Test #3:

score: 14
Accepted
time: 112ms
memory: 171192kb

input:

2
9250
403459 5
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
5...

output:

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

result:

ok ok

Test #4:

score: 14
Accepted
time: 75ms
memory: 155724kb

input:

2
120
55394 5
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:

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

result:

ok ok

Test #5:

score: 14
Accepted
time: 101ms
memory: 156820kb

input:

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

output:

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

result:

ok ok

Test #6:

score: 14
Accepted
time: 69ms
memory: 146748kb

input:

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

output:

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

result:

ok ok

Test #7:

score: 14
Accepted
time: 67ms
memory: 146848kb

input:

2
400
2260 5
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 5...

output:

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

result:

ok ok

Test #8:

score: 14
Accepted
time: 89ms
memory: 158160kb

input:

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

output:

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

result:

ok ok

Test #9:

score: 14
Accepted
time: 89ms
memory: 154956kb

input:

2
9078
76509 5
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:

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

result:

ok ok

Test #10:

score: 14
Accepted
time: 95ms
memory: 157404kb

input:

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

output:

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

result:

ok ok

Subtask #3:

score: 9
Accepted

Test #11:

score: 9
Accepted
time: 268ms
memory: 219920kb

input:

3
1769
481318 428631
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:

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

result:

ok ok

Test #12:

score: 9
Accepted
time: 195ms
memory: 167832kb

input:

3
5246
78503 54670
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:

12758
11231 3685 331 9602 7687 6346 2609 10 10253 5100 6047 2846 2578 9097 8089 8644 57 8272 10369 6613 10107 5848 10978 6730 3389 1125 2499 12603 869 8190 3100 3673 3518 1611 11544 3626 318 4695 5695 7307 9529 750 6357 7372 12446 9405 474 2278 6314 1457 7060 12269 8209 12570 8688 7280 11247 9190 56...

result:

ok ok

Test #13:

score: 9
Accepted
time: 188ms
memory: 149464kb

input:

3
396
1125 1442
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
5...

output:

160
21 78 52 13 20 139 76 43 99 91 102 55 5 49 32 127 126 93 1 80 140 30 26 68 96 76 31 35 129 71 46 9 105 37 75 107 43 44 72 59 13 39 19 96 39 2 74 16 142 35 22 14 29 54 77 64 20 34 123 60 61 152 65 122 8 108 87 60 10 73 117 40 110 42 148 20 41 14 97 124 132 86 118 22 112 11 4 74 17 103 95 7 36 12 ...

result:

ok ok

Test #14:

score: 9
Accepted
time: 193ms
memory: 149228kb

input:

3
487
1664 2238
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
5...

output:

558
148 539 427 218 210 412 136 249 112 376 184 292 235 294 148 216 341 269 302 180 94 295 544 71 492 201 268 450 299 312 395 4 71 173 303 343 527 393 249 442 127 267 350 55 80 167 246 314 94 352 51 428 308 117 297 388 34 249 202 205 143 60 104 333 99 209 475 467 72 463 109 409 472 7 526 9 505 488 1...

result:

ok ok

Test #15:

score: 9
Accepted
time: 312ms
memory: 223464kb

input:

3
130
498610 459330
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:

28970
4318 8170 75 18793 2819 24535 5912 6740 18682 4818 19326 10428 17989 1886 23653 16738 13423 27882 21722 21574 16371 3956 14455 4146 13139 7410 12024 8825 7108 2388 11289 1372 25393 19716 13582 14347 125 15782 11504 8941 17277 14518 3602 12360 21332 1999 19712 16414 19220 15401 13565 3011 4024 ...

result:

ok ok

Test #16:

score: 9
Accepted
time: 288ms
memory: 218688kb

input:

3
3566
462541 448340
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:

183
2 58 43 117 101 98 64 68 117 23 102 151 131 77 66 133 121 22 32 19 55 107 75 83 19 124 22 83 76 44 41 56 23 153 3 33 89 57 140 59 66 123 102 48 27 6 91 51 94 7 120 116 132 125 17 20 84 49 31 10 119 97 37 7 92 9 47 81 1 103 18 53 9 114 17 147 55 31 84 18 87 9 24 40 158 91 72 88 19 47 6 43 8 111 1...

result:

ok ok

Subtask #4:

score: 20
Accepted

Test #17:

score: 20
Accepted
time: 54ms
memory: 144812kb

input:

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

output:

839
1 576 577 2 578 579 580 581 582 583 3 584 585 586 587 575 589 590 591 592 593 2 594 595 1 596 597 598 599 2 600 562 549 550 1 551 1 552 1 553 554 555 556 557 558 559 560 5 561 548 563 564 565 566 567 568 569 7 570 571 572 573 574 588 628 629 1 630 631 2 632 633 634 635 636 637 638 639 627 641 64...

result:

ok ok

Test #18:

score: 20
Accepted
time: 40ms
memory: 144844kb

input:

4
26
910 955
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 5...

output:

417
161 281 233 397 332 69 57 300 92 133 122 172 283 368 56 198 131 134 282 185 392 322 163 9 116 256 141 179 325 10 261 38 193 4 165 323 210 370 199 206 103 56 33 255 15 301 272 20 39 251 63 229 9 244 46 108 152 17 223 280 202 101 281 97 113 223 1 280 24 66 353 22 18 6 398 54 361 175 308 167 58 318...

result:

ok ok

Test #19:

score: 20
Accepted
time: 46ms
memory: 149416kb

input:

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

output:

161
14 1 15 100 135 13 40 138 116 23 39 4 22 20 25 147 5 34 1 97 91 7 81 138 30 78 105 106 13 72 108 85 86 140 11 9 22 79 17 141 143 81 148 144 16 12 6 27 108 51 53 9 143 85 9 146 20 12 1 89 17 98 95 96 23 97 3 14 135 139 99 117 10 2 101 119 39 2 125 122 110 113 4 150 152 94 17 117 5 52 5 106 19 22 ...

result:

ok ok

Test #20:

score: 20
Accepted
time: 53ms
memory: 148956kb

input:

4
27
915 930
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 5...

output:

473
271 7 24 50 258 333 259 56 217 277 289 24 470 312 53 294 307 356 419 359 162 171 237 273 382 76 68 340 38 444 334 113 275 108 376 19 129 115 63 41 383 327 214 234 59 311 332 54 145 45 7 227 124 472 9 80 196 27 25 128 2 252 282 226 97 363 317 239 213 192 351 12 123 379 403 425 212 181 15 71 90 21...

result:

ok ok

Test #21:

score: 20
Accepted
time: 52ms
memory: 149276kb

input:

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

output:

196
79 82 147 178 126 142 141 139 137 127 149 61 128 152 153 68 15 130 133 161 162 95 1 98 160 99 101 23 103 158 156 106 4 107 108 93 110 111 3 113 115 10 116 1 144 120 148 121 145 122 123 124 186 5 119 25 118 117 194 184 114 11 112 169 146 105 104 102 100 2 179 181 125 97 96 30 94 129 138 140 136 1...

result:

ok ok

Test #22:

score: 20
Accepted
time: 33ms
memory: 144848kb

input:

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

output:

216
73 50 91 36 205 105 27 60 99 132 88 108 51 109 113 114 135 118 122 107 123 84 85 86 203 129 8 131 18 89 177 25 179 137 134 96 6 51 10 100 102 170 172 48 102 175 106 11 148 146 103 25 101 6 1 98 15 197 83 81 94 93 92 90 17 88 144 87 73 107 140 121 124 120 119 117 116 115 112 111 110 95 126 23 151...

result:

ok ok

Test #23:

score: 20
Accepted
time: 35ms
memory: 144824kb

input:

4
24
935 984
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 5...

output:

175
87 76 22 33 4 24 11 45 48 2 67 84 64 166 118 107 6 113 130 55 56 22 62 111 122 44 49 84 26 113 28 2 124 13 65 18 121 123 170 106 137 138 12 74 150 159 86 7 119 104 102 128 83 14 26 31 153 105 88 37 126 2 133 52 59 60 71 56 154 121 139 108 9 115 158 20 125 12 35 17 4 16 129 83 2 98 145 14 103 92 ...

result:

ok ok

Test #24:

score: 20
Accepted
time: 27ms
memory: 149008kb

input:

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

output:

588
557 502 476 479 498 480 456 459 461 2 465 460 420 519 424 25 428 4 490 438 445 483 442 434 427 426 481 419 446 31 565 422 560 586 443 439 537 500 416 429 26 35 10 447 448 336 337 577 54 338 339 342 343 344 345 347 532 335 554 6 10 545 357 551 552 359 509 34 308 524 309 311 403 534 314 315 316 31...

result:

ok ok

Test #25:

score: 20
Accepted
time: 47ms
memory: 146944kb

input:

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

output:

123
18 97 109 97 116 52 101 2 20 22 72 53 67 58 51 22 76 90 36 75 6 57 9 30 58 39 105 43 52 115 87 96 27 16 114 26 87 84 25 5 114 70 23 88 41 44 92 81 113 79 2 25 106 90 86 89 77 110 46 28 91 112 98 16 18 94 111 4 92 50 94 86 49 81 66 28 19 37 69 6 40 27 24 73 55 85 34 63 69 49 45 30 14 106 102 113 ...

result:

ok ok

Test #26:

score: 20
Accepted
time: 31ms
memory: 147244kb

input:

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

output:

648
140 274 536 556 571 546 612 4 17 425 367 403 42 497 244 519 514 25 507 183 448 447 464 465 13 1 34 466 467 468 395 469 470 22 42 471 472 264 463 474 475 476 477 478 479 480 481 453 444 445 2 446 308 4 449 450 251 451 315 452 49 272 443 454 455 45 456 457 345 458 31 146 459 412 9 351 460 461 28 4...

result:

ok ok

Test #27:

score: 20
Accepted
time: 33ms
memory: 146896kb

input:

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

output:

675
6 1 614 616 338 337 622 633 584 587 333 89 10 583 1 623 25 607 609 330 329 96 328 327 25 9 42 73 325 324 323 642 321 636 319 318 317 650 653 315 12 659 661 326 365 511 11 363 362 507 361 360 359 521 527 45 5 490 491 355 498 5 354 339 352 351 350 1 21 100 349 506 17 16 347 520 346 345 13 344 17 1...

result:

ok ok

Test #28:

score: 20
Accepted
time: 27ms
memory: 144848kb

input:

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

output:

377
373 35 213 7 40 210 203 350 197 111 54 313 233 27 18 306 10 225 159 158 154 51 151 150 148 16 144 299 186 296 7 180 137 162 163 164 165 4 58 168 347 171 172 173 174 175 176 13 178 1 341 336 75 335 79 187 188 189 332 329 185 131 326 323 153 136 5 138 321 320 2 319 143 322 324 325 1 152 155 156 32...

result:

ok ok

Test #29:

score: 20
Accepted
time: 49ms
memory: 145028kb

input:

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

output:

261
4 185 184 183 182 181 180 179 169 177 42 175 174 173 172 171 170 178 202 201 200 199 198 1 197 196 31 194 28 193 192 191 190 189 188 187 161 151 150 149 148 147 146 145 135 143 142 141 140 139 138 137 136 144 168 167 166 165 164 5 4 162 152 160 159 158 9 156 155 154 153 259 231 258 257 4 255 254...

result:

ok ok

Test #30:

score: 20
Accepted
time: 32ms
memory: 148800kb

input:

4
31
943 994
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 5...

output:

34
10 1 18 7 4 5 11 17 5 12 26 16 26 1 23 22 6 22 23 3 9 8 16 23 15 22 14 19 8 2 3 7 12 8 6 9 10 7 25 12 3 4 6 17 26 31 10 14 9 26 6 9 20 15 20 9 6 13 1 25 20 28 11 19 2 2 25 10 6 14 32 20 6 12 11 15 8 8 4 22 9 4 13 31 16 19 23 3 18 2 16 8 5 1 1 3 9 13 4 20 1 7 4 19 3 9 8 22 20 2 3 13 2 2 1 21 4 18 ...

result:

ok ok

Test #31:

score: 20
Accepted
time: 39ms
memory: 145232kb

input:

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

output:

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

result:

ok ok

Test #32:

score: 20
Accepted
time: 41ms
memory: 146900kb

input:

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

output:

150
16 128 4 129 104 130 8 131 79 80 13 51 133 10 56 134 19 136 13 92 104 100 70 65 133 78 141 76 142 85 144 113 41 94 147 139 18 14 116 4 12 125 103 35 109 27 1 34 69 1 74 9 19 38 27 35 50 91 6 24 105 96 3 70 74 79 3 117 80 108 2 102 97 28 77 66 47 18 87 39 52 81 123 124 46 11 100 103 61 6 66 61 4 ...

result:

ok ok

Subtask #5:

score: 22
Accepted

Dependency #4:

100%
Accepted

Test #33:

score: 22
Accepted
time: 134ms
memory: 161892kb

input:

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

output:

27238
9470 14241 23137 23294 30 46 23272 131 22705 22843 22969 23034 22937 22909 23995 23908 24191 23641 23458 157 23490 23793 23751 23832 21543 21519 21838 21259 21067 21354 21314 21334 22370 22413 22431 22262 22330 22587 22590 22605 22606 22561 22574 34 22614 22626 65 22545 22490 22498 22500 22458...

result:

ok ok

Test #34:

score: 22
Accepted
time: 173ms
memory: 183484kb

input:

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

output:

43611
673 23024 23023 23022 31200 31201 23021 31203 23020 6 31206 31196 23019 31209 23219 7147 31210 31211 31212 23018 31213 12872 23016 12880 31216 12878 23015 31217 155 31185 31174 23013 12877 23011 31178 12875 31180 12908 23009 31182 23008 23562 31173 31186 12898 12863 23006 23005 31188 23402 230...

result:

ok ok

Test #35:

score: 22
Accepted
time: 212ms
memory: 196092kb

input:

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

output:

58693
28072 39877 28073 28074 44525 49719 44526 6092 28078 28079 49718 28080 28071 28082 49717 49716 28085 28086 28087 5033 28088 1500 2599 4023 49712 28051 28052 28053 44528 49711 28056 28057 28058 28059 28060 6086 6082 28063 81 2546 49710 49709 49708 28068 28069 28070 51 28113 49707 28114 44531 49...

result:

ok ok

Test #36:

score: 22
Accepted
time: 91ms
memory: 152640kb

input:

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

output:

11000
2034 7704 7705 7706 50 7707 7708 8 7709 7710 7711 7712 7713 7703 11 7715 7716 18 7717 16 7718 7719 7720 7721 7722 7723 7724 7692 7681 7682 7683 69 7684 7685 5 7686 7687 7688 7689 67 7690 7691 7680 7693 7694 7695 7696 7697 7698 7699 7700 7701 7702 7714 7749 7750 7751 7752 7753 7754 7755 7756 77...

result:

ok ok

Test #37:

score: 22
Accepted
time: 103ms
memory: 155704kb

input:

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

output:

3386
1090 1581 2 2411 2245 2203 2315 566 2211 2309 304 262 240 509 1052 2424 2422 1216 2347 479 2235 517 2204 2294 156 333 1259 2284 389 2413 2240 2252 533 816 2295 844 533 2304 2215 2214 680 305 2247 2398 2391 2394 1261 23 2417 2344 2320 1047 2409 2421 1380 1359 2232 2237 2238 1148 68 541 2308 2312...

result:

ok ok

Test #38:

score: 22
Accepted
time: 106ms
memory: 150380kb

input:

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

output:

1051
838 565 933 888 411 290 779 414 415 774 770 769 889 419 890 787 788 794 793 922 425 935 789 783 275 782 944 765 390 703 886 771 392 772 764 394 775 777 396 907 753 388 812 998 400 876 810 402 867 869 405 800 407 390 882 11 22 25 128 321 866 41 703 436 276 732 75 235 881 346 357 180 180 32 785 7...

result:

ok ok

Test #39:

score: 22
Accepted
time: 81ms
memory: 150236kb

input:

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

output:

451
35 83 361 131 10 357 436 445 355 136 400 351 392 347 422 141 369 421 374 15 324 147 323 415 322 150 319 152 312 335 410 401 405 404 402 107 398 381 408 384 378 392 383 379 434 209 207 233 118 424 232 435 122 437 18 225 181 2 340 169 313 22 169 23 182 3 319 229 292 289 275 184 157 158 159 160 282...

result:

ok ok

Test #40:

score: 22
Accepted
time: 76ms
memory: 148248kb

input:

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

output:

118
73 68 103 111 43 86 96 83 104 82 95 21 92 80 78 108 114 115 100 51 38 84 49 97 89 106 105 109 91 85 81 79 50 113 107 101 102 77 90 98 99 87 110 116 3 14 94 14 10 1 49 75 12 27 112 32 117 52 40 93 45 44 59 37 61 7 54 88 67 43 46 11 66 118 77 10 56 21 41 65 63 74 1 75 64 22 27 34 19 69 70 24 1 40 ...

result:

ok ok

Test #41:

score: 22
Accepted
time: 81ms
memory: 146028kb

input:

5
227
1768 690
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:

345
323 164 169 169 80 15 132 87 116 110 239 248 190 29 109 314 131 260 85 124 272 273 128 104 55 269 260 141 266 103 64 108 305 290 143 52 230 208 157 136 298 27 276 149 172 154 225 22 230 44 217 236 22 88 245 223 131 51 84 279 57 87 181 293 200 289 134 106 144 110 197 272 42 62 229 48 4 171 194 8 ...

result:

ok ok

Test #42:

score: 22
Accepted
time: 88ms
memory: 148120kb

input:

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

output:

695
379 319 477 483 506 13 523 558 569 442 431 401 4 661 447 3 211 479 505 492 2 74 76 51 230 24 620 114 7 48 26 560 491 657 64 656 10 684 652 62 396 110 534 428 648 278 400 173 558 495 139 204 214 584 643 529 539 672 671 485 186 184 22 667 573 3 466 179 5 177 8 593 596 2 76 213 6 210 661 518 4 60 1...

result:

ok ok

Test #43:

score: 22
Accepted
time: 121ms
memory: 164160kb

input:

5
85
99108 97396
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
...

output:

48829
6616 47627 26033 19447 2451 12089 34881 10925 10825 25503 32408 30502 33340 4645 4344 13713 13830 44033 32568 9495 26767 22714 4966 20754 5835 26214 8896 5244 1535 36366 19474 7031 8959 26437 10625 417 14674 18021 17431 11750 35465 26067 15467 20892 28757 47413 25720 46170 28839 21695 14101 37...

result:

ok ok

Test #44:

score: 22
Accepted
time: 95ms
memory: 152680kb

input:

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

output:

126
8 2 87 88 89 90 91 5 92 93 85 95 17 96 97 98 9 99 100 101 14 1 69 70 71 31 7 73 74 75 76 68 1 79 80 81 94 83 11 84 102 121 2 126 125 124 123 1 30 119 118 10 117 21 115 114 1 112 111 110 109 108 107 9 105 104 103 82 19 8 20 52 15 32 22 22 23 24 25 26 2 28 29 30 31 32 33 34 41 28 10 2 3 4 5 6 7 8 ...

result:

ok ok

Test #45:

score: 22
Accepted
time: 100ms
memory: 158464kb

input:

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

output:

10182
5915 7706 7707 9480 7708 7709 7710 7711 7712 9639 7902 9349 9378 18 9495 6552 7148 9499 6547 9500 162 2959 6580 2983 6284 168 6569 2964 7684 8729 9179 3077 6264 6106 3101 6526 150 151 7690 213 6086 8484 9422 7695 7696 7697 2818 8999 2851 193 8408 9207 6457 8044 9411 6472 9457 7716 2803 8701 73...

result:

ok ok

Test #46:

score: 22
Accepted
time: 79ms
memory: 161840kb

input:

5
1256
83133 86248
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:

31782
4431 1610 17189 28583 16644 20631 28186 11040 115 17088 10728 19350 25915 11472 22261 15390 5159 2323 8979 28477 20054 24022 17356 23102 29672 19523 22121 18497 29700 17970 21908 11673 17936 13681 15117 12549 15000 21652 19669 5474 5106 11041 4727 11811 12039 24584 1781 2018 7903 1330 5924 208...

result:

ok ok

Test #47:

score: 22
Accepted
time: 88ms
memory: 152780kb

input:

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

output:

4114
3773 2800 3772 3771 3770 3768 3766 1312 3752 3762 3761 3760 3758 1316 3754 3793 3792 1299 3791 3787 3786 1977 3774 3783 3782 3781 3780 3777 3775 1220 2346 3742 1414 3730 3729 3728 3727 3104 3718 3717 3715 3714 217 3713 264 1790 3749 3747 1324 378 3741 3740 180 3738 3736 1332 1334 3733 3732 3785...

result:

ok ok

Test #48:

score: 22
Accepted
time: 91ms
memory: 155648kb

input:

5
443
9541 12325
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
...

output:

2862
2399 1598 416 990 236 396 178 2516 1250 1336 20 328 353 1468 1925 774 392 2294 416 1158 437 522 563 72 403 2743 2316 765 434 1383 2033 222 679 7 798 446 64 2834 1117 546 52 1584 1444 1027 1039 559 329 1841 137 2159 2556 2194 327 13 2445 222 929 1855 459 1687 1410 2049 2691 890 1646 481 2629 319...

result:

ok ok

Subtask #6:

score: 32
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #49:

score: 32
Accepted
time: 254ms
memory: 221332kb

input:

6
178
497927 412086
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:

120
44 5 9 8 68 8 2 93 55 61 69 37 27 105 82 1 75 11 77 15 12 87 14 31 52 82 33 46 82 10 115 5 97 52 84 96 37 70 15 92 2 48 16 15 3 26 75 89 8 42 69 35 47 57 99 38 106 4 41 1 28 107 1 21 80 13 8 3 1 71 68 7 26 58 36 64 8 54 91 58 6 73 57 22 71 24 20 23 88 66 56 34 25 91 33 88 18 17 29 74 13 67 38 21...

result:

ok ok

Test #50:

score: 32
Accepted
time: 352ms
memory: 227744kb

input:

6
3234
454553 464302
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:

232572
31357 2234 111263 172334 45976 15337 125600 229825 146767 91984 37255 113021 216483 23766 32123 122997 59526 147317 53402 148386 105359 11969 130549 46381 2532 50309 37387 131006 59463 175158 148022 102426 63571 128293 32394 218480 186060 90509 85853 3563 7103 176579 57341 109481 93437 145205...

result:

ok ok

Test #51:

score: 32
Accepted
time: 1116ms
memory: 258708kb

input:

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

output:

347915
292270 187502 300373 300279 304958 285829 346205 4458 319860 327002 329645 322528 217802 214819 228340 229273 220822 190205 204862 264073 268490 238909 242025 240375 240574 232835 236253 494 234802 270457 272346 226949 337738 299313 302903 2658 284593 1657 287949 288001 346081 345249 346779 3...

result:

ok ok

Test #52:

score: 32
Accepted
time: 790ms
memory: 226612kb

input:

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

output:

80099
475 42414 26185 26186 79948 79145 79117 26190 79066 3193 26194 80055 80065 80063 26197 696 79886 3640 79906 1391 26200 26202 26173 77496 26168 77479 1601 26169 77390 77775 1538 77842 77792 77686 77710 348 77030 77016 26177 29593 26178 77000 1000 26181 76886 77219 77284 5033 26224 77267 7058 29...

result:

ok ok

Test #53:

score: 32
Accepted
time: 396ms
memory: 223788kb

input:

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

output:

8376
7549 5417 7544 1598 3634 1823 4477 240 3242 173 4648 4922 2217 1100 7561 1542 5988 5763 1569 4568 455 1473 3075 4003 204 17 1388 14 7409 3306 3683 323 2087 3712 11 585 106 7428 1891 4549 7486 7502 544 5126 7459 3265 300 5843 578 5015 713 919 3071 7748 5852 2038 5775 8025 5546 8283 2879 1501 463...

result:

ok ok

Test #54:

score: 32
Accepted
time: 238ms
memory: 176720kb

input:

6
6213
156426 135199
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:

62086
13676 58458 51248 18076 9907 44301 35499 54885 46903 7157 61009 12841 21208 6427 235 27742 18437 43183 26463 4974 32800 25263 20949 34377 31877 15497 42567 1883 34799 22748 12989 27589 19170 41579 41270 65 2610 45317 41927 58993 2098 10899 48767 35355 18079 25236 1042 36090 57515 8665 45642 13...

result:

ok ok

Test #55:

score: 32
Accepted
time: 266ms
memory: 148256kb

input:

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

output:

604
2 1 501 7 495 533 457 5 76 471 453 492 533 470 13 471 109 110 16 525 527 474 468 516 461 530 456 46 480 7 481 477 454 204 458 529 466 1 528 59 527 472 514 236 240 241 475 136 138 9 3 6 3 158 28 1 170 171 476 479 524 544 378 547 180 178 11 56 382 383 384 386 4 387 199 388 552 496 183 389 519 485 ...

result:

ok ok

Test #56:

score: 32
Accepted
time: 274ms
memory: 146524kb

input:

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

output:

1521
808 605 809 27 807 806 805 1508 49 804 803 32 68 802 1518 792 800 799 798 61 34 1453 796 1486 795 106 1467 1220 2 39 9 794 793 801 11 1196 1197 19 826 825 13 824 823 1253 822 821 1268 820 4 810 34 1455 818 1457 817 816 165 815 38 45 814 813 812 209 8 42 811 1501 150 783 204 56 7 1272 1495 5 773...

result:

ok ok

Test #57:

score: 32
Accepted
time: 280ms
memory: 146300kb

input:

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

output:

747
665 378 524 632 525 528 529 662 661 16 635 636 657 639 655 537 538 540 641 96 543 6 644 499 647 642 502 503 505 648 508 638 510 511 614 5 6 615 516 517 518 520 552 15 17 572 650 10 576 20 587 583 691 69 690 688 10 579 620 14 577 26 578 582 612 38 35 585 680 551 560 553 5 626 555 557 2 558 547 56...

result:

ok ok

Test #58:

score: 32
Accepted
time: 273ms
memory: 148540kb

input:

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

output:

344
6 103 230 224 226 221 327 235 333 277 305 255 264 256 308 176 7 184 185 161 154 164 311 17 312 212 210 192 193 313 22 201 202 315 316 203 317 199 198 318 319 195 306 302 191 190 189 300 206 309 208 209 211 213 214 215 216 299 297 219 220 296 169 168 166 334 24 326 343 342 341 23 159 158 157 194 ...

result:

ok ok

Test #59:

score: 32
Accepted
time: 278ms
memory: 146452kb

input:

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

output:

730
304 576 8 2 577 578 579 580 581 582 393 1 16 584 202 585 586 130 7 589 32 590 21 408 7 140 348 593 594 62 596 158 141 41 387 356 125 382 550 551 139 172 553 554 555 89 194 346 556 38 41 558 36 559 121 62 11 128 394 147 26 385 348 70 86 245 150 569 570 34 380 216 572 573 51 127 56 627 192 13 267 ...

result:

ok ok

Test #60:

score: 32
Accepted
time: 335ms
memory: 228544kb

input:

6
2736
454986 470122
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:

204856
93853 159214 83590 44804 119809 161626 25378 5198 15127 105051 15561 169805 69263 63528 172615 106789 15155 35278 51902 93651 23420 33924 131588 169763 83038 64271 88958 7246 35827 81215 92365 68014 77404 118287 148420 30358 146831 85992 181171 94851 91071 15713 109010 989 93747 65908 82328 1...

result:

ok ok
English 繁體中文 简体中文

服务器时间: 2025-02-02 01:04:27 | 开源项目