QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61376#5020. 举办乘凉州喵,举办乘凉州谢谢喵Gemini7X100 ✓1666ms187016kbC++145.0kb2022-11-12 18:23:342022-11-12 18:23:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-12 18:23:36]
  • 评测
  • 测评结果:100
  • 用时:1666ms
  • 内存:187016kb
  • [2022-11-12 18:23:34]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
using namespace std;
const int maxn = 2e5 + 5, inf = 0x3f3f3f3f;
template <typename T>
void read(T &x) {
	T sgn = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <typename T>
void write(T x) {
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
void print(T x) {
	if (x < 0) putchar('-'), x = -x;
	write(x); putchar('\n');
}
bool _;
int n, m, ans[maxn], top[maxn], fa[maxn], son[maxn], sz[maxn], dep[maxn], D[maxn], rt, mn, anc[maxn];
int Rt[maxn], val[maxn << 5], ls[maxn << 5], rs[maxn << 5], tot;
int stk[maxn], num, c[maxn];
vector<int> vec[maxn], q3[maxn];
vector<pii> q[maxn], q2[maxn];
bool vis[maxn];
int bit[maxn];
bool __;
void add(int x, int v) { while (x <= n) bit[x] += v, x += x & -x; }
int qry(int x) { int ret = 0; while (x) ret += bit[x], x -= x & -x; return ret; }
void dfs1(int u) {
	sz[u] = 1;
	for (int v : vec[u]) {
		if (v == fa[u]) continue;
		fa[v] = u; dep[v] = dep[u] + 1;
		dfs1(v);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}
void dfs2(int u, int chain) {
	top[u] = chain;
	if (son[u]) dfs2(son[u], chain);
	for (int v : vec[u]) {
		if (v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
int LCA(int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
int dis(int u, int v) {
	return dep[u] + dep[v] - dep[LCA(u, v)] * 2;
}
void get_rt(int u, int ff, int ts) {
	sz[u] = 1;
	int mx = -inf;
	for (int v : vec[u]) {
		if (vis[v] || v == ff) continue;
		get_rt(v, u, ts);
		sz[u] += sz[v];
		mx = max(mx, sz[v]);
	}
	mx = max(mx, ts - sz[u]);
	if (mn > mx) rt = u, mn = mx;
}
void dfs3(int u, int ff, int d) {
	c[d]++;
	for (int v : vec[u]) {
		if (vis[v] || v == ff) continue;
		dfs3(v, u, d + 1);
	}
}
int MX;
void get_ans(int u, int ff, int op, int d) {
	for (int x : q3[u]) if (D[x] >= d) ans[x] += op * c[min(MX, D[x] - d)];
	for (int v : vec[u]) {
		if (vis[v] || v == ff) continue;
		get_ans(v, u, op, d + 1);
	}
}
void solve(int u, int ts) {
	vis[u] = 1;
	for (int i = 0; i <= ts; i++) c[i] = 0;
	dfs3(u, 0, 0);
	for (int i = 1; i <= ts; i++) c[i] += c[i - 1];
	MX = ts;
	get_ans(u, 0, 1, 0);
	for (int v : vec[u]) {
		if (vis[v]) continue;
		int tmp = (sz[u] < sz[v]) ? ts - sz[u] : sz[v];
		for (int i = 0; i <= tmp; i++) c[i] = 0;
		dfs3(v, u, 1);
		for (int i = 1; i <= tmp; i++) c[i] += c[i - 1];
		MX = tmp;
		get_ans(v, u, -1, 1);
	}
	for (int v : vec[u]) {
		if (vis[v]) continue;
		mn = inf; get_rt(v, u, (sz[u] < sz[v]) ? ts - sz[u] : sz[v]); anc[rt] = u;
		solve(rt, sz[v]);
	}
}
void ins(int x, int id, int op) {
	ans[id] += dep[x] * op;
	while (x) {
		q[x].eb(id, op);
		x = top[x];
		if (x != 1) q2[x].eb(id, -op);
		x = fa[x];
	}
}
void mdf(int &p, int l, int r, int pos, int v) {
	if (!p) p = ++tot;
	if (l == r) return val[p] += v, void();
	int mid = (l + r) >> 1;
	(pos <= mid) ? mdf(ls[p], l, mid, pos, v) : mdf(rs[p], mid + 1, r, pos, v);
	val[p] = val[ls[p]] + val[rs[p]];
}
int ask(int p, int l, int r, int x, int y) {
	if (!p || l > y || r < x) return 0;
	if (x <= l && r <= y) return val[p];
	int mid = (l + r) >> 1;
	return ask(ls[p], l, mid, x, y) + ask(rs[p], mid + 1, r, x, y);
}
int Merge(int u, int v) {
	if (!u || !v) return u | v;
	val[u] += val[v];
	ls[u] = Merge(ls[u], ls[v]);
	rs[u] = Merge(rs[u], rs[v]);
	return u;
}
void dfs4(int u) {
	for (int v : vec[u]) {
		if (v == fa[u]) continue;
		dfs4(v);
	}
	if (son[u]) for (auto x : q[u]) ans[x.fir] += x.sec * ask(Rt[son[u]], 1, n, 1, min(n, dep[son[u]] + D[x.fir] - 1));
	mdf(Rt[u], 1, n, dep[u], 1);
	for (int v : vec[u]) {
		if (v == fa[u]) continue;
		Rt[u] = Merge(Rt[u], Rt[v]);
	}
	for (auto x : q2[u]) ans[x.fir] += x.sec * ask(Rt[u], 1, n, 1, min(n, dep[u] + D[x.fir] - 1));
}
void clear() { for (int i = 1; i <= num; i++) add(stk[i], -1); num = 0; }
void dfs6(int u, int id) {
	stk[++num] = dep[u] - dep[id];
	add(stk[num], 1);
	for (int v : vec[u]) {
		if (v == fa[u]) continue;
		dfs6(v, id);
	}
}
void dfs5(int u) {
	for (int v : vec[u]) {
		if (v == fa[u] || v == son[u]) continue;
		dfs6(v, u);
	}
	for (auto x : q[u]) ans[x.fir] += x.sec * qry(min(D[x.fir], n));
	if (son[u]) dfs5(son[u]);
	for (int v : vec[u]) {
		if (v == fa[u] || v == son[u]) continue;
		clear(); dfs5(v);
	}
}
int main() {
	read(n);
	for (int i = 1, u, v; i < n; i++) {
		read(u); read(v);
		vec[u].pb(v); vec[v].pb(u);
	}
	read(m);
	dep[1] = 1; dfs1(1); dfs2(1, 1);
	for (int i = 1, x, y, z; i <= m; i++) {
		read(x); read(y); read(D[i]);
		z = LCA(x, y);
		q3[z].pb(i);
		ins(x, i, 1); ins(y, i, 1); ins(z, i, -2);
	}
	mn = inf; get_rt(1, 0, n); solve(rt, n);
	dfs4(1); dfs5(1);
	for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 15ms
memory: 35672kb

input:

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

output:

3226
2028
4988
208
252
3970
3886
2013
4974
2118
308
391
4768
312
4954
4988
4974
1551
4981
12
1856
4825
4974
4974
19
82
4960
4680
208
4870
474
3693
808
1880
213
3394
1203
266
84
4822
3334
70
81
4501
4960
668
4866
4974
113
490
75
163
209
2159
4981
4143
100
3168
232
66
4864
525
4958
390
4713
2305
15
49...

result:

ok 4966 numbers

Test #2:

score: 0
Accepted
time: 16ms
memory: 36356kb

input:

4914
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
27 54
27 ...

output:

3378
4914
231
4914
4914
3378
22
4914
4914
2559
4914
75
219
1407
1138
863
24
3890
4914
4914
399
399
13
139
77
4914
4095
3071
4914
23
151
110
1407
43
54
4914
4914
1919
2559
77
735
3071
24
133
479
4914
33
831
4
4914
4914
79
4914
199
3890
3071
73
567
15
75
21
126
4914
4914
203
4914
75
127
62
41
4914
409...

result:

ok 4975 numbers

Test #3:

score: 0
Accepted
time: 17ms
memory: 33572kb

input:

4921
1151 2767
2767 322
322 4451
4451 4867
4867 1265
1265 3197
3197 3890
3890 1052
1052 1407
1407 1578
1578 566
566 2965
2965 260
260 4908
4908 308
308 553
553 2845
2845 4249
4249 1284
1284 73
73 1088
1088 277
277 1878
1878 4128
4128 3609
3609 2126
2126 149
149 3467
3467 1653
1653 4913
4913 3604
360...

output:

4921
3192
3260
3983
949
2080
605
3471
4901
2020
2552
1570
3325
3643
458
1296
3072
3423
3045
2569
1720
3195
1908
4397
1536
2799
3072
2443
3176
3311
1403
1119
842
3028
2387
1903
2303
4921
2149
1974
4153
2053
2888
2344
3264
3709
3443
3601
2571
1207
4519
3745
959
1920
1305
1706
1743
522
1266
2153
1812
1...

result:

ok 4930 numbers

Test #4:

score: 0
Accepted
time: 15ms
memory: 31848kb

input:

4942
877 4180
4180 4409
4409 2233
2233 3491
3491 3459
3459 4501
4501 2192
2192 3539
3539 4379
4379 4346
4346 1553
1553 2100
2100 3426
3426 3461
3461 811
811 2981
2981 1493
1493 610
610 599
599 1741
1741 3216
3216 1646
1646 1016
1016 3757
3757 2570
2570 2900
2900 4649
4649 1014
1014 538
538 4288
4288...

output:

4236
3338
4942
4942
4942
4942
1551
1272
3885
4140
4942
3627
3132
3991
3157
4024
4942
4942
3761
3064
238
4942
4942
4942
4942
4942
2256
4942
649
4496
4942
4942
4491
866
4208
4942
4942
4726
4942
4462
4942
4942
4234
2676
2593
4942
4088
4942
2704
3344
3560
4942
4942
4461
4511
4634
3437
2884
3842
4942
494...

result:

ok 4910 numbers

Test #5:

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

input:

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

output:

4869
3419
3000
4640
4996
4996
3854
4165
4542
4996
1758
3584
3011
4996
4996
4383
2064
4199
2786
2470
4759
4996
4657
4157
2443
2594
1823
3215
1635
3908
1903
3207
2153
4448
4996
4996
3071
2649
3452
4996
1235
1599
2732
2244
2311
4618
1250
4577
3498
4941
1058
3498
3539
3415
907
4170
4996
4144
2235
2664
4...

result:

ok 4952 numbers

Test #6:

score: 0
Accepted
time: 17ms
memory: 30432kb

input:

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

output:

4442
4133
346
3268
4850
3512
3312
3581
4092
4655
2256
3950
3157
3480
4935
4188
4935
1593
1135
4935
4935
4875
4108
3771
4158
4935
4935
3156
3148
1814
4935
3368
4303
2861
4917
2370
3992
4764
2772
4935
4935
2640
4935
4691
2291
4268
1798
4530
3058
3219
4935
3141
4935
2699
4547
2164
2495
3049
370
3409
21...

result:

ok 4992 numbers

Test #7:

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

input:

4919
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 53
...

output:

2653
3219
4302
1418
1713
713
3341
647
487
1508
971
4851
4443
3078
2380
2267
4171
18
2056
1833
3136
817
4375
4103
3423
433
3967
725
282
2358
4171
1680
3350
2403
802
1855
137
2091
3731
1061
581
1273
4783
133
1911
4239
4233
678
3127
3481
284
1896
435
593
4781
103
4647
1615
1231
2689
574
1833
4783
645
4...

result:

ok 4980 numbers

Test #8:

score: 0
Accepted
time: 12ms
memory: 31680kb

input:

4973
1 4517
2 744
3 1115
4 3191
5 4186
6 4608
7 3898
8 3939
9 1998
10 2287
11 2277
12 4200
13 4935
14 3955
15 3683
16 278
17 547
18 3351
19 2642
20 4050
21 3457
22 2337
23 3435
24 1476
25 4853
26 3985
27 736
28 3016
29 4840
30 3866
31 4567
32 4067
33 3724
34 1872
35 1533
36 4787
37 53
38 1632
39 295...

output:

91
2487
2646
1791
2447
3327
532
1801
1079
1526
1236
77
4028
3401
4103
1573
3540
1641
452
52
2497
3128
2593
734
1293
3213
1786
1626
2130
2033
1935
2673
1758
1838
1284
758
2952
301
947
2875
3073
1462
2615
2842
3561
1969
1416
3088
2476
1082
696
3665
2041
3263
3063
2988
1402
1050
2967
3696
2309
3767
281...

result:

ok 4982 numbers

Subtask #2:

score: 8
Accepted

Test #9:

score: 8
Accepted
time: 1337ms
memory: 147076kb

input:

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

output:

757
69428
2793
181264
91707
182
32496
199183
6399
15975
11640
119051
236
689
15
9532
41
36592
178936
56
45424
193403
90248
3417
949
68
34133
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199153
155706
196287
192862
53742
51862
179199
428
196282
199989
3613
26
99007
134461
198159
20382
7518...

result:

ok 199996 numbers

Test #10:

score: 0
Accepted
time: 1504ms
memory: 187016kb

input:

199993
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
27 54
2...

output:

22
31743
62
30
510
6079
94
24063
190
4079
382
30
62
12159
1022
2043
8063
62
4
3063
4079
30
254
46
10
22
6111
12159
16127
22
1
12031
1
94
382
766
4063
254
46
766
1022
62
766
1
22
46
30
8063
8063
254
3063
22
62
30
1
62
254
4
10
15871
1022
46
2039
6079
22
254
1022
16127
30
766
8127
14
14
10
46
1
62
406...

result:

ok 199995 numbers

Test #11:

score: 0
Accepted
time: 1214ms
memory: 116600kb

input:

199993
25163 125238
125238 19096
19096 88864
88864 113505
113505 12722
12722 56225
56225 8736
8736 74926
74926 38529
38529 80231
80231 19719
19719 198784
198784 75213
75213 190174
190174 163340
163340 62363
62363 144160
144160 130912
130912 3919
3919 21218
21218 85281
85281 187312
187312 79930
79930...

output:

97095
57496
116181
132482
144412
69917
174677
96334
37980
80902
148979
22074
166530
153392
43419
163281
148526
62703
79363
199993
153733
152298
5085
156125
117973
61925
36346
95741
124148
102890
20093
5408
77598
176994
177809
169850
144418
43786
189237
69098
5167
199993
103575
105198
197612
38829
20...

result:

ok 199994 numbers

Test #12:

score: 0
Accepted
time: 907ms
memory: 123388kb

input:

200000
3219 118490
118490 61372
61372 74390
74390 88375
88375 63918
63918 37580
37580 33219
33219 170480
170480 81737
81737 153202
153202 93921
93921 149109
149109 88339
88339 167037
167037 67099
67099 58363
58363 6784
6784 109386
109386 11895
11895 14872
14872 65638
65638 43958
43958 181669
181669 ...

output:

59633
108235
72863
144596
90365
57521
48069
163045
124462
18633
39115
111210
59413
80420
86945
182373
99188
57011
148702
53778
132289
68037
69705
50797
91155
77852
27499
106082
87174
122445
78221
71755
10125
93101
163451
16175
104215
50130
81182
30091
44299
81429
91045
111890
73099
72278
74017
59177...

result:

ok 199992 numbers

Test #13:

score: 0
Accepted
time: 900ms
memory: 119316kb

input:

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

output:

40732
40074
40815
13444
89657
22422
23494
61358
102922
66209
62228
32272
77095
68562
27799
74336
45129
71632
68525
13022
71347
63735
92178
64200
90446
50728
83632
61441
43695
10496
35481
81587
75266
77943
56182
14188
46302
108160
84166
3192
52959
522
57676
28165
97982
15371
95012
3437
53633
49240
55...

result:

ok 199998 numbers

Test #14:

score: 0
Accepted
time: 683ms
memory: 121768kb

input:

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

output:

59224
71441
128293
104009
42824
136779
12532
93560
81095
108628
176617
63487
103752
175849
36193
178489
73311
34313
46423
75989
76344
145231
20076
127399
81148
17356
39455
99025
44904
3548
78503
135455
28
136931
58140
53161
33288
134084
67877
26048
51868
74301
139992
165315
126781
136117
28112
86333...

result:

ok 199996 numbers

Test #15:

score: 0
Accepted
time: 539ms
memory: 109504kb

input:

199997
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 5...

output:

65710
203
400
304
388
328
441
19
417
49
311
329
193
71968
895
179
152645
282
7600
185
150933
150045
444
3693
56770
34420
8765
335
73751
4665
3
203
380
44479
392
356
113
373
46663
143312
234
265
386
378
339
184360
404
21904
9861
393
445
441
91
299
9
213
24586
65263
22235
121
35761
169
36121
435
40035...

result:

ok 199995 numbers

Test #16:

score: 0
Accepted
time: 1666ms
memory: 137304kb

input:

199997
1 64008
2 4187
3 154904
4 191579
5 107782
6 29053
7 123085
8 191601
9 95335
10 164039
11 171804
12 145532
13 104884
14 19820
15 74055
16 14172
17 98802
18 144668
19 188276
20 173096
21 62815
22 133749
23 65035
24 161785
25 191028
26 84730
27 176488
28 173295
29 110316
30 121532
31 81037
32 81...

output:

135622
123942
47301
113894
93180
10469
9237
13166
2896
20323
182669
26483
168662
47202
7900
7785
129591
1577
17943
5638
16670
16980
32760
153668
394
142656
30298
1801
167880
25099
10860
39103
28660
158337
55
126816
57661
17387
11147
95051
3
13130
28040
163801
141
109445
110915
13173
56634
20527
6325...

result:

ok 199993 numbers

Subtask #3:

score: 23
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 23
Accepted
time: 1324ms
memory: 141872kb

input:

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

output:

190330
676
6
462
40
5
180041
3
9236
4
7780
72
19848
100092
66812
28617
39645
66797
22
12
957
2542
7
68308
382
96
217
50
44
227
12909
1519
54616
1682
27
124101
45
12279
173381
10
33
21516
147537
59
40
5332
183402
67257
4281
7
172420
498
154897
113480
208
174
1
497
172594
1098
788
13628
39540
3716
748...

result:

ok 199999 numbers

Test #18:

score: 0
Accepted
time: 1466ms
memory: 186196kb

input:

199996
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
27 54
2...

output:

1533
3063
6
30
23551
15871
15871
24063
30
16127
1022
12159
10
1021
254
14
190
12159
510
1533
190
8127
3055
1022
94
24063
766
766
94
254
38
62
8063
10
6
22
1533
24063
1531
1022
30
4079
6079
766
16127
190
2043
8127
510
62
126
8063
126
126
48444
15871
4079
16
6111
22
6
10
78
30
254
94
15871
4
254
1021
...

result:

ok 200000 numbers

Test #19:

score: 0
Accepted
time: 1126ms
memory: 118036kb

input:

199995
11041 115179
115179 153668
153668 847
847 108504
108504 29146
29146 69344
69344 97959
97959 9751
9751 161877
161877 181430
181430 34952
34952 189883
189883 115070
115070 183758
183758 82663
82663 166540
166540 32583
32583 98368
98368 134401
134401 177593
177593 20320
20320 84802
84802 71314
7...

output:

130387
9664
11547
91275
69020
68292
133814
4062
77306
61282
135928
73117
110236
103657
45122
57716
71794
147915
130944
51863
118043
70186
3280
145614
126093
73581
69331
53113
47390
148553
125773
9218
4978
58747
152237
79990
104530
37955
88353
26213
133365
186683
125906
71589
170278
141966
124506
906...

result:

ok 199990 numbers

Test #20:

score: 0
Accepted
time: 977ms
memory: 120484kb

input:

199993
177390 147612
147612 4211
4211 14815
14815 169902
169902 107796
107796 87432
87432 66581
66581 144789
144789 48284
48284 124832
124832 151850
151850 145877
145877 31550
31550 71569
71569 63733
63733 951
951 6788
6788 199487
199487 114893
114893 11399
11399 170687
170687 122411
122411 46734
46...

output:

107762
141285
24282
123780
66318
114627
45030
82414
56308
6384
104567
96050
91967
43940
151582
70456
69859
121641
60747
102655
183088
79543
155264
136617
108988
104594
43276
168667
110178
40707
29012
62994
22555
14804
27491
65920
22536
58571
192497
122141
47921
104042
112261
96620
126104
111319
9733...

result:

ok 199994 numbers

Test #21:

score: 0
Accepted
time: 926ms
memory: 118732kb

input:

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

output:

51578
38667
1524
13459
21140
3826
59246
2246
47429
55781
53983
77239
20185
106208
53791
70701
8913
35683
57133
100232
55601
50968
69940
56442
18980
6305
94853
29355
52681
96168
83317
11505
21769
51959
100713
61485
514
47185
100363
84120
36280
64865
55201
65700
7318
24265
82609
20438
5870
73828
86460...

result:

ok 199992 numbers

Test #22:

score: 0
Accepted
time: 673ms
memory: 119132kb

input:

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

output:

61674
63693
5444
4412
119192
97999
68341
140082
55497
42858
77523
54267
167822
49345
20816
48970
131851
179687
94880
43274
93973
118005
52804
91728
102191
94963
103067
30400
99910
161391
7340
68917
67420
88327
12228
104409
151035
80497
90523
116958
77993
61410
100229
69813
145161
121525
19553
14452
...

result:

ok 199992 numbers

Test #23:

score: 0
Accepted
time: 565ms
memory: 108948kb

input:

199991
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 5...

output:

59
48
415
291
69
119538
321
272
334
54
214
41286
367
13805
97857
104
241
255
283
91
323
161
357
125045
132
339
151823
80847
65651
115686
29503
218
53641
258
23
77332
288
45
73
66967
152
299
23692
98685
75
131750
139781
98
350
357
26
4232
254
178
57217
77332
239
448
11508
264
16540
398
117035
405
14
...

result:

ok 199993 numbers

Test #24:

score: 0
Accepted
time: 1454ms
memory: 137144kb

input:

199995
1 113414
2 2284
3 98845
4 44695
5 160127
6 100466
7 194555
8 16596
9 144228
10 80166
11 163524
12 104617
13 156298
14 190763
15 190200
16 51669
17 159037
18 3883
19 169292
20 129486
21 109285
22 177749
23 42088
24 110131
25 34729
26 20820
27 157541
28 11756
29 138395
30 24135
31 153422
32 191...

output:

109204
39278
62211
134886
9
601
181082
41676
2033
116851
72120
27639
11577
38351
77170
54255
33378
82327
102402
74545
8152
64128
31796
148495
415
54543
1354
47764
41935
52287
142939
122745
32683
1725
170345
41430
20010
48221
24637
34819
153209
10982
113155
18968
34947
162078
2043
106717
190000
1108
...

result:

ok 199999 numbers

Subtask #4:

score: 22
Accepted

Test #25:

score: 22
Accepted
time: 1128ms
memory: 129092kb

input:

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

output:

78
107329
190250
5672
110415
199160
3826
96672
75
13429
149
58
704
199639
25
190454
489
198350
197627
10273
172193
192719
99
191654
80328
481
195140
170809
120515
290
199616
719
142
195166
2607
20737
135444
199768
2433
164666
180527
198261
14511
53672
69060
185790
110874
639
131
2130
188357
150164
2...

result:

ok 199996 numbers

Test #26:

score: 0
Accepted
time: 1225ms
memory: 158048kb

input:

199992
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
27 54
2...

output:

1471
48440
199992
231
2687
31
114687
114687
13823
114
106495
163839
783
25599
199992
12799
73727
199992
431
196607
26623
414
27960
22
11135
60728
7551
167224
199992
231
199992
77823
25599
199992
15359
163839
15359
167224
113
4735
1439
45055
163839
391
56632
2159
24063
65
1439
383
62
57
1327
163839
4...

result:

ok 199992 numbers

Test #27:

score: 0
Accepted
time: 1098ms
memory: 112820kb

input:

199999
3860 158798
158798 118869
118869 87485
87485 146359
146359 191153
191153 55478
55478 180863
180863 50335
50335 96889
96889 48813
48813 98038
98038 187938
187938 87677
87677 134328
134328 38608
38608 80793
80793 70631
70631 193550
193550 97635
97635 158355
158355 67072
67072 186681
186681 1915...

output:

55240
49943
26982
45606
18199
8540
11154
152784
18240
110004
99804
184499
25817
43162
59012
69553
1005
100567
48973
134533
3623
46254
103686
19321
49467
116243
148782
4728
73635
54046
50253
112743
41598
15497
31081
115955
73228
101666
12285
66903
165797
10283
7127
8495
56070
15396
6405
64423
109109
...

result:

ok 200000 numbers

Test #28:

score: 0
Accepted
time: 900ms
memory: 121240kb

input:

199999
59863 94723
94723 191248
191248 161438
161438 39858
39858 77973
77973 71710
71710 106785
106785 362
362 86462
86462 133116
133116 123399
123399 4410
4410 92447
92447 47116
47116 51368
51368 1717
1717 15475
15475 40375
40375 180726
180726 185474
185474 93281
93281 27126
27126 126163
126163 185...

output:

28854
18939
99436
18961
67220
2913
72453
29640
46298
117130
151058
159698
48935
29930
80292
81462
64883
160737
96248
31383
139115
37518
45423
96863
4355
49922
35109
35647
43119
13322
143399
69774
113511
24821
58074
64681
120987
92287
36356
125547
47395
59340
70057
24681
70093
32217
92486
151556
272
...

result:

ok 199998 numbers

Test #29:

score: 0
Accepted
time: 815ms
memory: 111896kb

input:

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

output:

179063
34801
103836
135654
64719
31996
62273
36156
57204
102674
112750
26298
26560
36095
4538
136764
59099
25262
22520
2188
326
124414
49430
104026
13192
107883
19919
11694
36861
12879
46288
44653
63915
43067
53333
25512
51864
95866
48607
75013
30475
45557
43145
122747
1292
92281
16134
106448
96618
...

result:

ok 199996 numbers

Test #30:

score: 0
Accepted
time: 603ms
memory: 118340kb

input:

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

output:

11322
92512
102000
97896
20730
48162
17704
111224
70792
61672
38774
3548
82674
7220
63754
48942
110298
166606
80194
89338
20980
39184
530
64760
57858
74920
4682
32684
103882
62806
138544
57050
47356
20632
13396
76936
14736
49600
169188
141804
62220
9794
7876
87336
70928
4802
88372
38652
33414
57390
...

result:

ok 199999 numbers

Test #31:

score: 0
Accepted
time: 445ms
memory: 100680kb

input:

199997
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 5...

output:

1782
4982
5806
6770
3651
1082
268
2432
3191
6471
5869
3261
7666
2045
2623
5952
6615
4034
2808
1757
1553
8402
5288
1726
3113
9374
8519
4150
7828
9439
8409
6435
9101
3764
3702
503
151
7328
6347
6911
6963
2134
3879
6229
7721
6562
4477
1305
8052
4024
6810
7220
5699
8918
6330
1719
3279
3201
6052
7004
621...

result:

ok 199999 numbers

Test #32:

score: 0
Accepted
time: 1210ms
memory: 122668kb

input:

199999
1 133395
2 64415
3 65341
4 81009
5 84535
6 162775
7 10569
8 14377
9 16311
10 131379
11 199183
12 64100
13 71522
14 115723
15 167988
16 184640
17 163581
18 20948
19 25356
20 107507
21 9188
22 137361
23 2343
24 110749
25 28698
26 136381
27 19371
28 44461
29 6620
30 81748
31 199467
32 23686
33 4...

output:

5308
12623
377
5650
2217
3364
8277
11398
3252
6806
9983
2090
9100
7471
20364
1528
7894
593
8848
3908
4789
3727
2719
9300
5056
2535
7723
3027
9920
14537
6965
6119
13888
10319
6801
2961
4206
8834
8531
14022
2293
3721
3857
9070
7956
2671
1097
8434
4441
2794
9169
3865
1060
2150
8676
175
5869
8878
7828
9...

result:

ok 199992 numbers

Subtask #5:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #33:

score: 20
Accepted
time: 197ms
memory: 50136kb

input:

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

output:

49991
27842
12698
41582
41674
49129
139
49931
49986
49966
33701
41907
520
7
49823
37296
45378
43279
22
45415
43709
139
1658
12239
1106
48337
42014
49964
1603
49935
1295
38134
484
49771
13800
36652
12183
1503
49825
148
49211
195
46766
38915
49990
26440
26888
1176
140
37080
8196
5750
49964
49612
49935...

result:

ok 49997 numbers

Test #34:

score: 0
Accepted
time: 245ms
memory: 57432kb

input:

49994
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
27 54
27...

output:

13823
49994
49994
24
367
48
19455
367
2175
6655
1215
3839
17407
9727
49994
28671
49994
3039
49994
49151
1071
3839
3839
49994
1215
49994
671
3839
49994
591
3711
49994
15359
49994
28
2175
367
28671
10751
49994
11263
98
107
41802
4543
199
36863
49994
49994
1183
367
49151
40959
1071
2111
6655
11263
1927...

result:

ok 49997 numbers

Test #35:

score: 0
Accepted
time: 215ms
memory: 52648kb

input:

49992
18276 49801
49801 29872
29872 18038
18038 5160
5160 47615
47615 9368
9368 48020
48020 18919
18919 22293
22293 28784
28784 26366
26366 16335
16335 996
996 28965
28965 7132
7132 9570
9570 22976
22976 16634
16634 22619
22619 28051
28051 11004
11004 1360
1360 41340
41340 43214
43214 24436
24436 46...

output:

46017
14490
35283
47122
47076
47522
33249
14538
36480
29309
30496
22079
35856
47676
19688
29847
49992
46968
30446
36597
41074
24827
42181
37491
49992
33422
23462
34849
43986
32605
22539
43614
40945
48216
9983
37908
40591
47737
22962
33035
23333
35206
19572
33241
18254
44132
21667
21688
43981
44138
3...

result:

ok 49996 numbers

Test #36:

score: 0
Accepted
time: 156ms
memory: 53932kb

input:

49991
36788 8430
8430 29122
29122 7462
7462 34863
34863 38520
38520 38159
38159 10299
10299 26846
26846 40569
40569 35453
35453 39237
39237 37963
37963 2323
2323 5574
5574 49072
49072 8151
8151 9543
9543 14269
14269 15375
15375 38098
38098 46141
46141 29199
29199 13837
13837 3056
3056 13396
13396 20...

output:

10717
26965
17476
49991
49991
12680
32753
49991
44617
49991
49991
49991
49991
29760
49991
49991
49991
49991
49991
49991
15545
49991
19088
21948
23809
49991
46952
49991
49991
49991
36059
37144
49991
49991
41837
49991
49991
49991
49991
49991
49991
49991
49991
49991
49991
49991
28977
43912
49991
49991
...

result:

ok 49999 numbers

Test #37:

score: 0
Accepted
time: 162ms
memory: 50144kb

input:

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

output:

49992
44208
40560
49983
44985
19872
12959
21712
45703
31309
33201
49992
21924
36480
16502
31883
16181
36221
24725
42191
49992
35236
49992
35558
23642
20260
20165
11056
7575
49992
47236
49992
49992
43883
49992
35916
44169
49992
32253
41307
11731
4410
36173
36842
41712
18415
15542
34255
14712
35964
31...

result:

ok 49997 numbers

Test #38:

score: 0
Accepted
time: 118ms
memory: 51580kb

input:

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

output:

39583
37249
43384
29100
15677
17788
5806
32912
32417
42927
35958
35935
20363
17412
28393
13083
49992
17231
44476
34557
26645
31001
33105
49992
42169
38467
49992
34467
22711
30648
32377
40585
16552
48257
37613
16909
35471
49992
25468
18922
26730
24191
41997
49299
41755
17953
37963
49992
2358
9448
499...

result:

ok 49991 numbers

Test #39:

score: 0
Accepted
time: 80ms
memory: 47992kb

input:

49992
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 53...

output:

2119
8453
47550
40224
8275
48438
21511
29343
11178
12840
37338
17769
49992
40224
26178
11775
11405
48882
23283
9518
26016
49548
36450
8684
22461
35730
41556
10352
38656
26589
8503
36628
20425
46879
43554
47994
15804
12373
28369
21219
43776
38004
38886
35562
20679
5674
16613
25704
29120
2178
21055
31...

result:

ok 49990 numbers

Test #40:

score: 0
Accepted
time: 218ms
memory: 50872kb

input:

49996
1 34528
2 1933
3 8542
4 37866
5 13181
6 33418
7 31611
8 9600
9 47851
10 22729
11 34920
12 20679
13 13874
14 35815
15 1308
16 40327
17 20697
18 34642
19 45144
20 40726
21 36899
22 49440
23 42507
24 34983
25 34496
26 41651
27 19121
28 30392
29 48080
30 18302
31 28030
32 22472
33 26275
34 17680
3...

output:

177
25075
32138
400
36791
38592
28612
12464
10352
43337
36452
43158
13659
5593
29988
23224
7087
23922
25697
21833
5923
44766
33658
16893
26217
30297
37628
43546
12097
2042
26157
34289
36173
22194
3792
36001
44332
6645
23987
19246
32699
8178
25580
8650
32659
39845
21279
24361
32241
26532
20586
3931
3...

result:

ok 49996 numbers

Subtask #6:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #41:

score: 20
Accepted
time: 1145ms
memory: 131424kb

input:

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

output:

179995
108586
4963
70151
689
198956
197533
15818
172427
118
52593
199983
198743
199323
162610
144870
162893
36041
525
199998
6091
15211
199998
199939
1707
199993
33565
199838
115776
198285
195716
2734
126920
199940
196726
196524
47829
199558
114808
18326
197686
14180
1394
19
191283
176946
5606
124
1...

result:

ok 199999 numbers

Test #42:

score: 0
Accepted
time: 1143ms
memory: 158500kb

input:

199992
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
27 54
2...

output:

199992
56
199992
13055
11135
199992
163839
431
799
199992
727
199992
199992
431
4863
1471
196607
199992
33
2367
199992
1471
106495
199992
1471
199992
199992
199992
199992
9151
199992
2623
199992
231
199992
199992
199992
783
431
45055
199992
26623
423
431
14847
199992
34815
90111
1083
431
199992
1999...

result:

ok 199992 numbers

Test #43:

score: 0
Accepted
time: 1119ms
memory: 114424kb

input:

200000
118825 47656
47656 65863
65863 74743
74743 199221
199221 111383
111383 107539
107539 47816
47816 169853
169853 102993
102993 101994
101994 33240
33240 25914
25914 69791
69791 77751
77751 120707
120707 172811
172811 193635
193635 18418
18418 10680
10680 47074
47074 197767
197767 150332
150332 ...

output:

200000
64650
93758
56301
50503
118402
148383
83228
129609
90886
75758
200000
69251
127325
159115
118795
150796
166706
64322
153404
150739
50524
112623
158834
196078
64809
116702
145625
150839
83880
138037
173583
127876
72942
102044
155630
200000
112467
196660
177109
132219
70774
134923
190720
76880
...

result:

ok 199993 numbers

Test #44:

score: 0
Accepted
time: 911ms
memory: 126276kb

input:

200000
140177 147015
147015 80766
80766 173562
173562 145745
145745 115382
115382 81887
81887 134802
134802 31260
31260 42937
42937 3026
3026 143880
143880 70228
70228 106613
106613 64162
64162 73444
73444 158592
158592 127118
127118 134344
134344 120280
120280 80902
80902 103224
103224 124428
12442...

output:

200000
200000
59622
91201
68717
200000
151534
84875
149153
200000
41840
200000
200000
158096
106034
89586
200000
200000
154987
54783
124204
151075
183769
200000
200000
200000
110986
186654
151730
180598
200000
200000
167338
200000
200000
200000
181651
165751
158064
200000
83213
200000
17633
200000
7...

result:

ok 199999 numbers

Test #45:

score: 0
Accepted
time: 815ms
memory: 111372kb

input:

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

output:

102287
62949
83320
78317
119816
120129
175292
197099
153372
83521
118966
89093
116052
62696
134790
108942
69628
193383
123944
151060
27792
71146
109472
81289
68534
85601
125191
58074
90875
58204
143224
131193
105748
196859
68706
174117
134837
53880
84743
98881
177935
61478
123596
199996
55478
107385...

result:

ok 199993 numbers

Test #46:

score: 0
Accepted
time: 733ms
memory: 116832kb

input:

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

output:

186807
109497
139615
191555
184979
162897
124317
103761
187612
57874
68832
121596
141626
160741
48560
109825
199998
32708
199998
102262
199998
173769
46050
126461
101135
32016
199998
199998
125655
131367
199998
119037
186247
199998
94814
142975
139522
56868
199998
103410
33688
143220
156222
153369
1...

result:

ok 199998 numbers

Test #47:

score: 0
Accepted
time: 472ms
memory: 99272kb

input:

199992
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 5...

output:

48861
134946
43510
54859
148817
190647
96145
183527
36169
18973
13027
68842
106516
136659
172809
97806
6923
65669
158162
82067
94501
119877
173292
118474
127433
171957
52421
175517
148807
130127
10699
116764
52985
165727
193317
158162
93183
36616
58892
164392
10328
28633
116277
145209
121227
70707
1...

result:

ok 199996 numbers

Test #48:

score: 0
Accepted
time: 1273ms
memory: 126312kb

input:

199998
1 18131
2 108742
3 195033
4 176233
5 48568
6 43435
7 141282
8 149515
9 33524
10 51760
11 192173
12 12860
13 23308
14 32202
15 85869
16 126977
17 95377
18 66385
19 57539
20 116394
21 127394
22 170730
23 70332
24 135810
25 31748
26 131929
27 30606
28 149494
29 82156
30 179350
31 25065
32 11486
...

output:

29024
185228
193197
130227
91464
160018
124481
32790
186358
174038
56523
108354
110289
94210
108442
72790
161588
163272
96168
65303
58425
65093
169744
150289
6440
60395
146279
4201
165286
44100
106156
17362
45113
85568
61972
139648
26506
100065
6858
166513
71469
147775
5859
34022
174902
104135
14275...

result:

ok 199991 numbers