QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#327226#3307. Query on a Tree 17james1BadCreeperWA 152ms27176kbC++143.2kb2024-02-14 20:43:312024-02-14 20:43:33

Judging History

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

  • [2024-02-14 20:43:33]
  • 评测
  • 测评结果:WA
  • 用时:152ms
  • 内存:27176kb
  • [2024-02-14 20:43:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int N = 1e5 + 5; 

int n, q, f[17][N], sz[N], son[N];
int top[N], dfn[N], dep[N], num, idx[N];  
vector<int> G[N]; 

void dfs1(int x, int fa) {
    dep[x] = dep[f[0][x] = fa] + 1; sz[x] = 1; 
    for (int i = 1; i <= 16; ++i) f[i][x] = f[i - 1][f[i - 1][x]]; 
    for (int y : G[x]) if (y != fa) {
        dfs1(y, x); sz[x] += sz[y]; 
        if (sz[y] > sz[son[x]]) son[x] = y; 
    }
}
void dfs2(int x, int tp) {
    top[x] = tp; idx[dfn[x] = ++num] = x; 
    if (!son[x]) return; dfs2(son[x], tp); 
    for (int y : G[x]) if (y != son[x] && y != f[0][x]) dfs2(y, y); 
}

i64 T[N * 4], tag[N * 4]; 
inline void pushup(int o) { T[o] = T[o << 1] + T[o << 1 | 1]; }
inline void maketag(int o, int l, int r, int k) { T[o] += 1ll * (r - l + 1) * k; tag[o] += k; }
inline void pushdown(int o, int l, int r) {
    if (!tag[o]) return; int mid = l + r >> 1; 
    maketag(o << 1, l, mid, tag[o]); maketag(o << 1 | 1, mid + 1, r, tag[o]); 
    tag[o] = 0; 
}
void update(int o, int l, int r, int x, int y) {
    if (l == r) return maketag(o, l, r, 1), void(); 
    pushdown(o, l, r); int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, y); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y); 
    pushup(o); 
}
i64 query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o]; 
    pushdown(o, l, r); int mid = l + r >> 1; i64 res = 0; 
    if (x <= mid) res += query(o << 1, l, mid, x, y); 
    if (mid < y) res += query(o << 1 | 1, mid + 1, r, x, y); 
    return res; 
}
int search(int o, int l, int r, i64 s) {
    if (l == r) return idx[l]; 
    pushdown(o, l, r); int mid = l + r >> 1; 
    if (s <= T[o << 1]) return search(o << 1, l, mid, s); 
    return search(o << 1 | 1, mid + 1, r, s - T[o << 1]); 
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); 
    cin >> n; 
    bool _26 = 1; 
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y; 
        if (i == 1 && x == 66827) _26 = 0; 
        G[x].emplace_back(y); G[y].emplace_back(x); 
    }
    dfs1(1, 0); dfs2(1, 1); 
    if (!_26) return 0; 
    cin >> q; 
    while (q--) {
        int op, x, y; cin >> op >> x; 
        if (op == 1) update(1, 1, n, dfn[x], dfn[x] + sz[x] - 1); 
        else {
            cin >> y; 
            if (_26) {
                while (top[x] != top[y]) {
                    if (dep[top[x]] < dep[top[y]]) swap(x, y); 
                    update(1, 1, n, dfn[top[x]], dfn[x]); 
                    x = f[0][top[x]]; 
                }
                if (dep[x] < dep[y]) swap(x, y); 
                update(1, 1, n, dfn[y], dfn[x]); 
            }
        }
        if (_26) {
            i64 sum = T[1] / 2 + 1; 
            x = search(1, 1, n, sum); 
            if (query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1) >= sum) cout << x << '\n'; 
            else {
                for (int i = 16; i >= 0; --i) if (f[i][x]) {
                    y = f[i][x]; 
                    if (query(1, 1, n, dfn[y], dfn[y] + sz[y] - 1) < sum) x = y; 
                }
                cout << f[0][x] << '\n'; 
            }
        }
    }
    return 0; 
}

详细

Test #1:

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

input:

7
1 6
1 7
7 3
3 2
7 5
5 4
4
1 2
1 4
1 6
2 6 7

output:

2
7
7
1

result:

ok 4 lines

Test #2:

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

input:

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

output:

2
2
2
2
2
2
2
2
2
2
2

result:

ok 11 lines

Test #3:

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

input:

2
1 2
1
1 1

output:

1

result:

ok single line: '1'

Test #4:

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

input:

2
1 2
1
2 1 2

output:

1

result:

ok single line: '1'

Test #5:

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

input:

100
1 2
58 2
2 87
63 87
65 63
65 19
6 87
58 21
87 8
87 74
91 6
95 65
2 61
87 59
3 61
37 87
67 87
23 2
63 9
87 46
40 67
70 2
12 58
46 75
75 36
28 3
12 33
72 87
39 6
75 52
85 70
1 76
26 40
47 28
2 49
41 65
66 28
51 37
15 47
86 51
8 60
97 19
48 58
72 90
33 83
97 54
36 5
23 14
78 52
90 7
99 2
48 82
48 6...

output:

72
3
3
87
87
2
2
2
2
87
87
87
87
87
2
87
87
87
87
87
87
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87...

result:

ok 10000 lines

Test #6:

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

input:

100
27 1
27 35
96 1
54 35
25 54
81 35
69 25
27 18
69 83
27 99
70 83
81 61
1 77
73 54
35 68
61 89
20 89
99 95
37 20
63 95
95 38
7 83
63 78
86 35
89 13
71 77
70 14
95 34
13 62
24 95
77 98
99 33
25 100
36 63
35 8
65 54
66 83
40 8
15 81
78 59
15 4
62 28
97 14
15 58
69 3
89 44
47 100
52 73
12 95
53 38
39...

output:

46
35
46
83
83
83
83
35
35
35
25
25
25
35
25
25
25
25
25
54
54
35
35
35
54
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
35
...

result:

ok 10000 lines

Test #7:

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

input:

100
1 19
19 45
58 45
58 72
36 45
45 94
94 13
90 58
64 90
90 23
45 12
90 52
27 36
19 42
72 35
23 32
67 36
1 18
54 36
33 67
10 1
55 90
54 65
92 72
53 42
65 24
9 45
81 42
85 35
8 81
10 44
85 68
23 30
69 12
43 69
23 25
12 88
85 99
91 9
24 100
48 81
60 94
33 41
52 51
17 19
51 82
30 49
32 28
52 7
82 79
82...

output:

33
45
45
45
45
45
58
58
58
58
58
45
58
45
58
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
...

result:

ok 10000 lines

Test #8:

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

input:

100
67 1
34 67
34 72
26 72
63 26
26 14
63 24
63 49
42 14
45 34
14 71
71 87
71 7
14 22
64 72
90 7
14 58
87 99
33 87
24 70
65 64
42 30
33 74
99 62
3 71
60 90
84 90
40 70
47 45
84 69
89 7
57 3
99 59
66 65
58 76
37 14
6 37
72 54
38 24
15 99
51 84
93 76
59 8
89 53
75 51
97 99
20 8
28 53
95 15
11 53
95 13...

output:

21
37
14
14
14
14
71
14
14
14
14
14
14
14
14
14
14
14
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
14
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
71
...

result:

ok 10000 lines

Test #9:

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

input:

100
1 56
1 65
50 1
50 4
4 8
4 27
31 8
10 50
25 10
31 28
31 64
97 25
44 64
16 4
44 89
43 64
89 23
33 43
37 33
10 13
90 43
26 37
97 39
16 52
10 12
20 39
33 78
36 37
37 34
79 1
34 3
20 32
25 77
81 78
35 20
82 25
35 19
35 74
5 20
63 39
38 43
37 66
89 42
57 19
3 18
19 69
100 90
59 69
45 78
34 88
69 60
35...

output:

77
50
77
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
10
10
10
10
10
10
10
10
50
50
50
10
50
50
50
10
50
50
50
10
50
50
50
10
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
4
4
4
4
4
50
50
50
50
50
50
50
50
50
50
50
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4...

result:

ok 10000 lines

Test #10:

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

input:

100
1 13
4 1
57 4
13 30
4 73
30 78
30 25
28 30
64 57
4 52
25 83
66 64
99 64
21 28
25 98
28 14
28 7
99 39
13 71
74 99
7 31
14 72
72 45
74 68
79 83
79 93
83 20
11 30
4 95
7 18
86 83
88 68
72 6
32 30
97 95
90 7
89 97
99 29
26 90
90 5
66 67
90 91
49 30
90 51
87 39
28 24
5 22
72 38
50 24
80 74
88 9
81 95...

output:

50
30
28
30
28
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
...

result:

ok 10000 lines

Test #11:

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

input:

100
11 1
1 46
1 55
46 65
43 46
84 1
11 73
77 46
1 78
46 92
81 55
28 55
11 6
1 16
14 78
95 46
1 18
22 77
10 73
65 88
37 11
34 6
14 32
74 16
16 27
43 58
89 1
50 1
55 30
11 38
45 55
92 33
67 78
92 75
80 22
73 23
79 43
69 28
25 78
85 11
65 82
77 99
32 97
2 16
65 62
42 73
46 72
83 58
67 53
100 28
14 51
3...

output:

40
77
46
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
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
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
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
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...

result:

ok 10000 lines

Test #12:

score: 0
Accepted
time: 4ms
memory: 13840kb

input:

100
1 17
78 17
1 24
17 34
24 70
67 24
78 36
17 13
94 1
1 32
36 80
17 50
15 1
78 92
53 78
32 79
28 1
34 30
21 50
67 49
62 67
25 15
61 80
94 73
36 72
71 13
67 85
46 15
13 54
70 4
28 3
33 24
32 18
79 19
5 32
26 73
99 94
75 33
39 25
63 71
61 84
29 73
100 17
5 88
2 34
3 6
68 92
4 11
5 82
39 23
49 69
87 5...

output:

31
1
31
32
32
32
32
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
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
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
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 10000 lines

Test #13:

score: 0
Accepted
time: 4ms
memory: 15940kb

input:

100
95 1
87 1
95 72
99 95
76 1
67 95
54 1
50 72
94 95
1 29
99 78
52 54
25 1
27 76
27 48
18 50
48 32
54 9
44 29
31 72
63 50
36 95
57 99
81 99
52 39
29 47
28 94
47 42
87 93
98 78
16 32
44 12
18 100
34 57
20 95
31 70
63 13
69 31
9 17
68 47
76 49
48 30
95 71
44 56
14 94
2 50
98 43
79 49
53 87
8 81
75 52...

output:

14
95
95
95
95
95
95
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
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
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
1
1
1
1
1
1
1
1
1
1
1
95
1
95
95
95
95
95
1
95
95
95
95
95
1
95
1
1
1
1
1
95
95
95
95
95
1
1
1
1
1
...

result:

ok 10000 lines

Test #14:

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

input:

100
43 1
4 43
90 4
90 9
56 9
56 53
57 53
57 74
47 74
47 27
25 27
25 62
44 62
44 12
81 44
81 87
88 12
21 87
42 87
42 18
31 42
18 67
41 31
21 71
71 30
60 41
17 60
26 41
96 17
96 100
100 94
86 94
50 94
39 94
35 86
82 39
100 55
3 100
92 30
20 86
3 93
22 20
14 20
99 82
93 79
50 33
15 22
58 15
79 36
15 32...

output:

20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
20
20
20
86
20
20
20
86
86
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
86
86
86
86
20
20
...

result:

ok 10000 lines

Test #15:

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

input:

100
1 5
98 5
82 98
2 82
98 47
47 77
40 77
40 38
38 99
38 32
59 32
59 50
94 50
94 88
45 94
51 45
15 88
55 45
73 45
8 55
83 8
57 83
81 83
55 11
90 8
62 11
11 12
36 90
62 30
48 30
36 20
36 25
27 25
17 25
24 30
42 25
25 52
84 42
42 95
65 42
42 33
33 16
74 95
63 65
63 22
22 13
65 70
13 64
85 70
22 43
79 ...

output:

77
77
35
55
55
55
42
42
42
42
65
65
65
65
85
85
85
85
31
85
85
85
85
65
65
65
85
65
65
65
65
65
65
65
65
65
65
65
85
85
85
85
85
85
85
85
93
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
65
65
65
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
...

result:

ok 10000 lines

Test #16:

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

input:

100
61 1
61 14
14 21
21 15
21 5
65 5
5 64
64 77
80 77
58 80
80 85
18 85
58 13
29 13
79 29
12 79
12 66
66 48
95 66
95 33
95 76
76 49
93 49
88 93
83 49
88 17
57 48
88 3
3 25
25 9
9 71
71 75
75 6
97 6
97 26
26 28
87 71
6 78
86 28
86 81
24 17
81 94
37 24
94 54
37 4
35 81
67 4
94 10
67 46
10 47
73 10
19 ...

output:

85
80
88
88
9
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
9
9
9
88
9
25
25
88
88
88
25
88
25
25
25
25
9
9
71
71
75
71
71
71
71
71
75
71
71
71
71
71
71
71
71
71
71
71
75
75
6
75
75
71
75
71
75
71
75
71
71
71
71
71
71
71
71
71
71
9
9
25
25
25
25
88
25
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
8...

result:

ok 10000 lines

Test #17:

score: 0
Accepted
time: 4ms
memory: 15924kb

input:

100
8 1
93 1
66 1
82 1
88 1
1 96
77 1
8 38
8 70
19 1
1 20
1 43
1 95
1 80
1 29
92 1
56 1
71 1
8 73
62 82
1 78
1 87
8 76
1 45
22 77
8 6
54 1
1 46
1 58
50 66
34 1
28 93
66 30
66 15
38 85
1 9
93 61
8 16
66 48
93 14
93 90
27 1
21 1
93 44
1 60
8 51
66 65
95 84
4 8
83 88
32 93
11 8
40 88
1 74
1 7
96 35
93 ...

output:

6
8
8
8
8
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
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
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
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
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
...

result:

ok 10000 lines

Test #18:

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

input:

100
1 66
76 1
41 1
1 6
1 38
67 66
31 1
91 1
1 96
42 1
1 5
41 16
1 30
59 66
28 76
1 58
66 43
41 68
1 48
78 1
1 60
72 76
61 1
15 1
94 1
66 27
1 4
38 29
38 20
23 66
10 76
36 6
75 41
37 1
6 13
19 76
76 35
1 18
1 86
1 49
44 1
1 64
6 85
1 39
80 5
1 71
1 7
66 34
56 41
76 92
65 91
8 76
41 33
99 6
1 51
93 58...

output:

87
1
87
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
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
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
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
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
...

result:

ok 10000 lines

Test #19:

score: 0
Accepted
time: 4ms
memory: 15940kb

input:

100
1 25
72 1
1 16
1 96
55 1
11 1
26 1
2 1
1 37
8 25
72 6
1 4
1 13
46 25
31 1
99 1
21 1
1 10
52 1
83 72
86 1
16 22
49 16
72 80
76 1
1 15
35 1
44 25
33 1
66 11
91 11
43 72
85 1
7 1
54 72
94 1
50 16
32 16
28 72
1 20
16 59
1 48
14 72
84 25
16 17
58 1
63 26
97 25
57 55
65 26
61 16
19 1
16 92
95 1
2 74
1...

output:

78
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
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
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
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
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...

result:

ok 10000 lines

Test #20:

score: 0
Accepted
time: 152ms
memory: 23356kb

input:

100000
1 33107
1 49683
49683 23838
33107 33841
25927 23838
1 74779
99345 74779
36731 99345
23838 70246
38975 49683
36605 74779
49283 1
72218 49283
36605 89277
16724 49283
15597 89277
74779 70693
25927 10882
18787 49683
49283 89923
74779 18891
18891 72904
70246 64950
74779 39040
51544 39040
48338 722...

output:

89754
28789
33107
33107
49683
49683
49683
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
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
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
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
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #21:

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

input:

100000
1 98526
98526 71881
71881 32316
71881 91701
97004 71881
1 50154
50154 25648
90382 32316
98526 51008
81074 71881
88290 91701
20835 81074
1 88584
81163 1
5066 98526
63220 71881
5066 43945
88290 89171
97004 78551
49986 91701
53367 88584
50154 89663
50154 90725
98456 89663
90382 74858
90725 53584...

output:

94781
47260
71881
66830
1649
81074
20703
66830
66830
66830
35108
20703
66830
66830
20703
20703
20703
20703
20703
20703
20703
20703
20703
66830
66830
20703
20703
1649
1649
1649
1649
1649
1649
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
81074
8...

result:

ok 100000 lines

Test #22:

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

input:

100000
98458 1
18530 1
95442 1
98458 2967
97766 95442
18530 5382
5382 45839
97766 70789
97766 46371
51056 70789
2100 5382
97766 40344
193 98458
18530 45452
2967 91534
5382 71051
68600 5382
65092 2967
43663 70789
66738 1
20267 95442
2100 61712
39565 66738
95442 56590
29031 61712
8607 91534
91681 5105...

output:

98813
97766
97766
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
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
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
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 90ms
memory: 23568kb

input:

100000
1 93030
48178 93030
1655 1
93030 95380
15742 95380
15742 38782
49563 93030
93030 94593
38782 10482
94593 62811
62811 38444
62630 93030
23379 1
66269 95380
15320 66269
69627 1
93030 637
10482 46696
62570 66269
43085 69627
40421 15320
40421 29280
38444 29544
13323 29280
15320 51097
13323 33995
...

output:

57889
1
1
1
93030
93030
93030
1
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
93030
9303...

result:

ok 100000 lines

Test #24:

score: 0
Accepted
time: 98ms
memory: 23600kb

input:

100000
1 46788
46788 74831
38318 46788
46788 28121
28121 85162
46788 24705
62068 1
46788 86508
24705 85078
80001 24705
91029 80001
62068 55738
62068 11972
62068 80422
11972 36665
36665 81942
28121 85074
85078 35507
85074 93487
46788 65180
2803 46788
67158 85074
11972 30193
6547 36665
67785 55738
543...

output:

10039
1
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
46788
4678...

result:

ok 100000 lines

Test #25:

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

input:

100000
1 86599
1715 1
86599 79823
65172 1715
93401 79823
18478 1
95324 18478
1534 79823
86599 40049
18478 84772
88749 40049
33592 84772
20450 93401
72786 33592
54506 79823
49207 20450
20450 52827
40049 32100
51159 1
51159 69551
52827 83745
1974 51159
7678 32100
2139 93401
53523 69551
26607 40049
847...

output:

90253
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
86599
1
1
1
1
1
86599
1
1
1
86599
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
86599
86599
86599
1
86599
1
86599
1
86599
86599
86599
1
86599
86599
86599
86599
86599
86599
86599
86599
86599
86599
86599
86599
8659...

result:

ok 100000 lines

Test #26:

score: -100
Wrong Answer
time: 36ms
memory: 27176kb

input:

100000
66827 1
66827 3020
37001 3020
86421 37001
48188 86421
48188 66366
64459 66366
64459 70776
70776 88217
88217 53546
53546 60759
94219 60759
52771 94219
52771 1872
1872 33491
33491 15705
78366 15705
68591 78366
68591 70054
70054 94898
94898 37055
83477 37055
83477 61881
61881 39144
39144 70057
7...

output:


result:

wrong answer 1st lines differ - expected: '75000', found: ''