QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#293784#7855. 不跳棋JWRuixi100 ✓847ms194668kbC++174.1kb2023-12-29 19:04:342023-12-29 19:04:35

Judging History

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

  • [2023-12-29 19:04:35]
  • 评测
  • 测评结果:100
  • 用时:847ms
  • 内存:194668kb
  • [2023-12-29 19:04:34]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
// #define ATC
#define IL inline
#define LL long long
#define eb emplace_back
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FIO(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
using namespace std;

#ifdef ATC
#include <atcoder/all>
using namespace atcoder;
#endif

namespace IO {
	char ibuf[1 << 20], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 20, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
	inline long long read() {
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}
	template<typename _Tp>
	inline void write(_Tp x) {
		static char stk[64], *top = stk;
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		do *top++ = x % 10, x /= 10;
		while (x);
		while (top != stk) putchar((*--top) | 48);
	}
}

using IO::read;
using IO::write;

using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define MP make_pair

constexpr int N = 5e5 + 9, INF = 1e9 + 7;
int n, typ, sz[N], son[N];
vector<int> G[N];

struct vNode {
	int v;
	LL c;
	vNode (int v = INF, LL c = 0) : v(v), c(c) {}
	vNode operator + (const vNode &z) const {
		return v < z.v ? *this : v > z.v ? z : vNode(v, c + z.c);
	}
	vNode& operator += (const vNode &z) {
		return *this = *this + z;
	}
};

/**
 * Cluster
 * x : upper
 * y : lower
 * all : dis(x, y)
 * v : min length
 * u : min length to x
 * d : min length to y
*/

struct cNode {
	enum {I, C, R} typ = I;
	int x, y, all;
	vNode v, u, d;
};

cNode C (const cNode &a, const cNode &b) {
	cNode c;
	c.typ = cNode::C;
	c.x = a.x, c.y = b.y;
	c.all = a.all + b.all;
	c.u = a.u + vNode(a.all + b.u.v, b.u.c);
	c.d = b.d + vNode(b.all + a.d.v, a.d.c);
	c.v = a.v + b.v + vNode(a.d.v + b.u.v, a.d.c * b.u.c);
	return c;
}

cNode R (const cNode &a, const cNode &b) {
	cNode c;
	c.typ = cNode::R;
	c.x = a.x, c.y = a.y;
	c.all = a.all;
	c.u = a.u + b.u;
	c.d = a.d + vNode(a.all + b.u.v, b.u.c);
	c.v = a.v + b.v + vNode(a.u.v + b.u.v, a.u.c * b.u.c);
	return c;
}

#define ls(p) tr[p].lc
#define rs(p) tr[p].rc

int rt, tot;

struct TNode {
	int lc, rc, p, sz;
	cNode v;
} tr[N << 2];

IL void dfs1 (int u, int fa) {
	sz[u] = 1;
	tr[u].v = cNode{cNode::I, fa, u, 1, vNode(), vNode(1, 1), vNode(0, 1)};
	tr[u].sz = 1;
	if (u > 1) {
		G[u].erase(find(G[u].begin(), G[u].end(), fa));
	}
	for (int v : G[u]) {
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

IL int bld (vi::iterator L, vi::iterator R, auto F) {
	if (L == R - 1) {
		return *L;
	}
	int all = 0;
	for (auto i = L; i != R; ++i) {
		all += tr[*i].sz;
	}
	vi::iterator mid = L + 1;
	int sum = 0;
	for (auto i = L; i != R; ++i) {
		sum += tr[*i].sz;
		if (sum <= all / 2) {
			mid = i + 1;
		}
	}
	int x = bld(L, mid, F), y = bld(mid, R, F);
	++tot;
	ls(tot) = x, rs(tot) = y;
	tr[x].p = tot, tr[y].p = tot;
	tr[tot].sz = tr[x].sz + tr[y].sz;
	tr[tot].v = F(tr[x].v, tr[y].v);
	return tot;
}

IL int dfs2 (int u) {
	vi vc{u};
	for (int p = u; son[p]; p = son[p]) {
		vi ve{son[p]};
		for (int v : G[p]) {
			if (v != son[p]) {
				ve.eb(dfs2(v));
			}
		}
		vc.eb(bld(ve.begin(), ve.end(), R));
	}
	return bld(vc.begin(), vc.end(), C);
}

int main() {
	n = read(), typ = read();
	for (int i = 1, u, v; i < n; i++) {
		u = read(), v = read();
		G[u].eb(v);
		G[v].eb(u);
	}
	dfs1(1, 0);
	tot = n, rt = dfs2(1);
	LL as = 0;
	for (int i = 1; i < n - 1; i++) {
		LL u = read();
		if (typ) {
			u ^= as;
		}
		tr[u].v.v = tr[u].v.u = tr[u].v.d = vNode();
		for (u = tr[u].p; u; u = tr[u].p) {
			tr[u].v = (tr[u].v.typ == cNode::C ? C : R)(tr[ls(u)].v, tr[rs(u)].v);
		}
		writesp(tr[rt].v.v.v), writeln(as = tr[rt].v.v.c);
	}
}
// I love WHQ!

详细

Test #1:

score: 4
Accepted
time: 12ms
memory: 171444kb

input:

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

output:

1 97
1 94
1 93
1 92
1 91
1 89
1 88
1 85
1 84
1 83
1 82
1 81
1 79
1 77
1 76
1 75
1 73
1 70
1 69
1 68
1 67
1 67
1 67
1 67
1 66
1 65
1 64
1 63
1 62
1 61
1 61
1 60
1 58
1 57
1 57
1 52
1 51
1 50
1 47
1 44
1 41
1 39
1 38
1 37
1 36
1 35
1 34
1 29
1 27
1 26
1 26
1 26
1 25
1 24
1 23
1 22
1 22
1 21
1 20
1 18
...

result:

ok 98 lines

Test #2:

score: 4
Accepted
time: 7ms
memory: 171448kb

input:

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

output:

1 94
1 91
1 90
1 89
1 84
1 83
1 80
1 78
1 77
1 76
1 73
1 72
1 68
1 66
1 66
1 65
1 65
1 62
1 60
1 58
1 54
1 53
1 52
1 51
1 50
1 49
1 47
1 46
1 45
1 40
1 39
1 36
1 36
1 36
1 35
1 34
1 32
1 28
1 27
1 27
1 27
1 27
1 27
1 27
1 24
1 23
1 23
1 21
1 21
1 20
1 20
1 20
1 20
1 19
1 19
1 19
1 18
1 16
1 15
1 14
...

result:

ok 98 lines

Test #3:

score: 4
Accepted
time: 7ms
memory: 171492kb

input:

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

output:

1 95
1 94
1 92
1 89
1 87
1 84
1 82
1 79
1 74
1 73
1 71
1 68
1 66
1 64
1 62
1 61
1 59
1 58
1 56
1 55
1 54
1 51
1 50
1 50
1 50
1 49
1 49
1 48
1 46
1 45
1 41
1 39
1 38
1 35
1 33
1 32
1 30
1 28
1 28
1 27
1 27
1 25
1 22
1 20
1 20
1 19
1 19
1 19
1 17
1 13
1 13
1 13
1 12
1 12
1 12
1 11
1 11
1 10
1 10
1 10
...

result:

ok 98 lines

Test #4:

score: 4
Accepted
time: 8ms
memory: 171436kb

input:

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

output:

1 998
1 997
1 996
1 994
1 992
1 990
1 988
1 980
1 979
1 977
1 976
1 974
1 970
1 969
1 966
1 961
1 956
1 955
1 954
1 951
1 950
1 948
1 947
1 944
1 943
1 942
1 940
1 938
1 935
1 934
1 931
1 929
1 928
1 927
1 923
1 922
1 921
1 920
1 919
1 918
1 916
1 915
1 912
1 909
1 904
1 903
1 902
1 901
1 901
1 898
...

result:

ok 998 lines

Test #5:

score: 4
Accepted
time: 16ms
memory: 171544kb

input:

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

output:

1 997
1 996
1 995
1 994
1 990
1 987
1 985
1 984
1 981
1 980
1 975
1 973
1 971
1 970
1 969
1 968
1 966
1 965
1 964
1 963
1 962
1 961
1 960
1 959
1 957
1 956
1 954
1 953
1 952
1 951
1 945
1 944
1 943
1 941
1 939
1 937
1 933
1 931
1 930
1 928
1 926
1 925
1 924
1 921
1 920
1 920
1 918
1 917
1 916
1 914
...

result:

ok 998 lines

Test #6:

score: 4
Accepted
time: 23ms
memory: 171492kb

input:

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

output:

1 997
1 996
1 992
1 986
1 985
1 984
1 983
1 982
1 981
1 979
1 976
1 973
1 971
1 966
1 963
1 962
1 958
1 956
1 953
1 952
1 949
1 948
1 947
1 946
1 944
1 943
1 942
1 941
1 941
1 940
1 939
1 938
1 935
1 933
1 932
1 931
1 930
1 929
1 928
1 925
1 923
1 921
1 920
1 920
1 919
1 916
1 914
1 911
1 908
1 906
...

result:

ok 998 lines

Test #7:

score: 4
Accepted
time: 262ms
memory: 180508kb

input:

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

output:

1 199998
1 199997
1 199995
1 199992
1 199990
1 199989
1 199988
1 199985
1 199983
1 199980
1 199979
1 199976
1 199975
1 199973
1 199972
1 199971
1 199968
1 199967
1 199959
1 199957
1 199955
1 199954
1 199953
1 199952
1 199950
1 199948
1 199947
1 199945
1 199944
1 199943
1 199942
1 199941
1 199940
1 1...

result:

ok 199998 lines

Test #8:

score: 4
Accepted
time: 267ms
memory: 180488kb

input:

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

output:

1 199997
1 199996
1 199992
1 199990
1 199988
1 199986
1 199985
1 199981
1 199980
1 199979
1 199978
1 199977
1 199976
1 199974
1 199973
1 199971
1 199970
1 199966
1 199964
1 199963
1 199962
1 199961
1 199960
1 199958
1 199957
1 199956
1 199954
1 199953
1 199949
1 199947
1 199946
1 199945
1 199943
1 1...

result:

ok 199998 lines

Test #9:

score: 4
Accepted
time: 247ms
memory: 180572kb

input:

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

output:

1 199996
1 199995
1 199992
1 199989
1 199988
1 199987
1 199986
1 199984
1 199980
1 199975
1 199974
1 199973
1 199971
1 199970
1 199969
1 199968
1 199963
1 199961
1 199958
1 199955
1 199953
1 199951
1 199950
1 199948
1 199947
1 199945
1 199942
1 199938
1 199936
1 199931
1 199930
1 199928
1 199927
1 1...

result:

ok 199998 lines

Test #10:

score: 4
Accepted
time: 175ms
memory: 189300kb

input:

200000 0
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
52...

output:

1 199997
1 199995
1 199993
1 199991
1 199989
1 199987
1 199985
1 199983
1 199981
1 199979
1 199977
1 199975
1 199973
1 199971
1 199969
1 199967
1 199965
1 199963
1 199961
1 199959
1 199957
1 199955
1 199953
1 199951
1 199949
1 199947
1 199945
1 199943
1 199941
1 199939
1 199937
1 199935
1 199933
1 1...

result:

ok 199998 lines

Test #11:

score: 4
Accepted
time: 171ms
memory: 181900kb

input:

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

output:

1 199997
1 199995
1 199992
1 199988
1 199985
1 199983
1 199981
1 199979
1 199978
1 199976
1 199974
1 199972
1 199971
1 199970
1 199967
1 199964
1 199962
1 199961
1 199959
1 199956
1 199954
1 199951
1 199949
1 199946
1 199943
1 199942
1 199940
1 199939
1 199936
1 199935
1 199934
1 199933
1 199929
1 1...

result:

ok 199998 lines

Test #12:

score: 4
Accepted
time: 176ms
memory: 181824kb

input:

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

output:

1 199996
1 199995
1 199992
1 199989
1 199986
1 199985
1 199983
1 199982
1 199981
1 199980
1 199979
1 199976
1 199974
1 199971
1 199969
1 199966
1 199961
1 199960
1 199957
1 199954
1 199953
1 199950
1 199949
1 199946
1 199943
1 199942
1 199938
1 199937
1 199936
1 199935
1 199933
1 199931
1 199929
1 1...

result:

ok 199998 lines

Test #13:

score: 4
Accepted
time: 173ms
memory: 189352kb

input:

200000 1
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
52...

output:

1 199997
1 199995
1 199993
1 199991
1 199989
1 199987
1 199985
1 199983
1 199981
1 199979
1 199977
1 199975
1 199973
1 199971
1 199969
1 199967
1 199965
1 199963
1 199961
1 199959
1 199957
1 199955
1 199953
1 199951
1 199949
1 199947
1 199945
1 199943
1 199941
1 199939
1 199937
1 199935
1 199933
1 1...

result:

ok 199998 lines

Test #14:

score: 4
Accepted
time: 177ms
memory: 189252kb

input:

200000 1
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
52...

output:

1 199997
1 199995
1 199993
1 199991
1 199989
1 199987
1 199985
1 199983
1 199981
1 199979
1 199977
1 199975
1 199973
1 199971
1 199969
1 199967
1 199965
1 199963
1 199961
1 199959
1 199957
1 199955
1 199953
1 199951
1 199949
1 199947
1 199945
1 199943
1 199941
1 199939
1 199937
1 199935
1 199933
1 1...

result:

ok 199998 lines

Test #15:

score: 4
Accepted
time: 106ms
memory: 189260kb

input:

200000 1
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
52...

output:

1 199997
1 199995
1 199993
1 199991
1 199989
1 199987
1 199985
1 199983
1 199981
1 199979
1 199977
1 199975
1 199973
1 199971
1 199969
1 199967
1 199965
1 199963
1 199961
1 199959
1 199957
1 199955
1 199953
1 199951
1 199949
1 199947
1 199945
1 199943
1 199941
1 199939
1 199937
1 199935
1 199933
1 1...

result:

ok 199998 lines

Test #16:

score: 4
Accepted
time: 179ms
memory: 189260kb

input:

200000 1
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
52...

output:

1 199997
1 199995
1 199993
1 199991
1 199989
1 199987
1 199985
1 199983
1 199981
1 199979
1 199977
1 199975
1 199973
1 199971
1 199969
1 199967
1 199965
1 199963
1 199961
1 199959
1 199957
1 199955
1 199953
1 199951
1 199949
1 199947
1 199945
1 199943
1 199941
1 199939
1 199937
1 199935
1 199933
1 1...

result:

ok 199998 lines

Test #17:

score: 4
Accepted
time: 248ms
memory: 180548kb

input:

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

output:

1 199998
1 199997
1 199996
1 199994
1 199991
1 199990
1 199989
1 199988
1 199986
1 199985
1 199984
1 199982
1 199981
1 199978
1 199977
1 199974
1 199973
1 199970
1 199968
1 199963
1 199962
1 199961
1 199958
1 199957
1 199956
1 199955
1 199954
1 199949
1 199948
1 199947
1 199944
1 199942
1 199938
1 1...

result:

ok 199998 lines

Test #18:

score: 4
Accepted
time: 234ms
memory: 180600kb

input:

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

output:

1 199997
1 199992
1 199991
1 199990
1 199989
1 199986
1 199984
1 199982
1 199980
1 199979
1 199976
1 199975
1 199972
1 199971
1 199970
1 199969
1 199966
1 199965
1 199964
1 199962
1 199960
1 199954
1 199953
1 199950
1 199949
1 199948
1 199945
1 199944
1 199943
1 199942
1 199941
1 199940
1 199938
1 1...

result:

ok 199998 lines

Test #19:

score: 4
Accepted
time: 190ms
memory: 181840kb

input:

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

output:

1 199996
1 199995
1 199993
1 199992
1 199990
1 199987
1 199985
1 199983
1 199982
1 199980
1 199979
1 199978
1 199977
1 199974
1 199973
1 199971
1 199968
1 199964
1 199960
1 199957
1 199955
1 199950
1 199948
1 199947
1 199944
1 199943
1 199941
1 199939
1 199938
1 199935
1 199933
1 199932
1 199931
1 1...

result:

ok 199998 lines

Test #20:

score: 4
Accepted
time: 193ms
memory: 182856kb

input:

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

output:

1 199997
1 199996
1 199994
1 199993
1 199992
1 199991
1 199987
1 199985
1 199984
1 199983
1 199981
1 199979
1 199976
1 199973
1 199971
1 199969
1 199968
1 199966
1 199964
1 199960
1 199958
1 199956
1 199955
1 199953
1 199950
1 199947
1 199945
1 199943
1 199942
1 199940
1 199936
1 199934
1 199931
1 1...

result:

ok 199998 lines

Test #21:

score: 4
Accepted
time: 490ms
memory: 194668kb

input:

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

output:

2 124999250001
2 124998750003
2 124998250006
2 124997750010
2 124997250015
2 124996750021
2 124996250028
2 124995750036
2 124995250045
2 124994750055
2 124994250066
2 124993750078
2 124993250091
2 124992750105
2 124992250120
2 124991750136
2 124991250153
2 124990750171
2 124990250190
2 124989750210
...

result:

ok 499998 lines

Test #22:

score: 4
Accepted
time: 811ms
memory: 192584kb

input:

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

output:

1 499998
1 499997
1 499995
1 499994
1 499993
1 499992
1 499991
1 499990
1 499988
1 499987
1 499986
1 499985
1 499983
1 499981
1 499977
1 499976
1 499974
1 499973
1 499971
1 499970
1 499969
1 499968
1 499965
1 499957
1 499949
1 499948
1 499947
1 499946
1 499941
1 499939
1 499938
1 499934
1 499933
1 4...

result:

ok 499998 lines

Test #23:

score: 4
Accepted
time: 847ms
memory: 192616kb

input:

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

output:

1 499998
1 499997
1 499996
1 499994
1 499989
1 499987
1 499986
1 499985
1 499979
1 499975
1 499974
1 499972
1 499971
1 499970
1 499967
1 499966
1 499965
1 499964
1 499963
1 499961
1 499959
1 499958
1 499956
1 499952
1 499946
1 499943
1 499942
1 499940
1 499939
1 499938
1 499934
1 499933
1 499932
1 4...

result:

ok 499998 lines

Test #24:

score: 4
Accepted
time: 786ms
memory: 192536kb

input:

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

output:

1 499998
1 499997
1 499995
1 499994
1 499990
1 499987
1 499986
1 499985
1 499984
1 499983
1 499981
1 499980
1 499979
1 499977
1 499976
1 499975
1 499973
1 499972
1 499967
1 499964
1 499962
1 499961
1 499959
1 499957
1 499955
1 499954
1 499953
1 499952
1 499951
1 499949
1 499948
1 499947
1 499944
1 4...

result:

ok 499998 lines

Test #25:

score: 4
Accepted
time: 776ms
memory: 192540kb

input:

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

output:

1 499992
1 499988
1 499987
1 499986
1 499985
1 499984
1 499982
1 499978
1 499977
1 499976
1 499974
1 499972
1 499971
1 499970
1 499969
1 499967
1 499966
1 499965
1 499960
1 499958
1 499957
1 499955
1 499947
1 499941
1 499940
1 499933
1 499932
1 499931
1 499928
1 499927
1 499926
1 499925
1 499924
1 4...

result:

ok 499998 lines