QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#763369	#9607. 熟练	ANIG	100 ✓	1772ms	332552kb	C++14	2.8kb	2024-11-19 19:50:44	2024-11-19 19:50:45

Judging History

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

[2024-11-19 19:50:45]
评测

测评结果：100
用时：1772ms
内存：332552kb

查看

[2024-11-19 19:50:44]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int op,t,n,m,mk[N],tot,fa[N][20],rs[N],dep[N],dfn[N],eds[N],idx;
vector<int>p[N];
vector<tuple<int,int,int> >g[N];
set<int>q,jl[N];
void dfs(int x){
	mk[x]=1;dfn[x]=++idx;
	for(int i=1;i<=19;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(auto c:p[x]){
		if(mk[c])continue;
		fa[c][0]=x;
		dep[c]=dep[x]+1;
		dfs(c);
	}
	eds[x]=idx;
	mk[x]=0;
}
int up(int x,int k){
	while(k){
		x=fa[x][__lg(k&-k)];
		k^=k&-k;
	}
	return x;
}
int lca(int a,int b){
	if(dep[a]>dep[b])swap(a,b);
	b=up(b,dep[b]-dep[a]);
	if(a==b)return a;
	for(int i=19;i>=0;i--){
		if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];
	}
	return fa[a][0];
}
struct msg{
	int op,x,y;
};
vector<msg>st;
vector<pair<int,int> >qs[N];
void upt(msg x){
	if(x.op==0){
		jl[x.x].insert(x.y);
		q.insert(x.x);
	}else{
		jl[x.x].erase(jl[x.x].find(x.y));
		if(!jl[x.x].size())q.erase(q.find(x.x));
	}
}
void solve(int x){
	mk[x]=1;
	int lst=st.size();
	for(auto [a,b,bh]:g[x]){
	//	cout<<x<<" "<<bh<<endl;
		int op=1;
//		for(auto c:q){
//			for(auto d:jl[c])cout<<c<<"-"<<d<<endl;
//		}
		if(q.lower_bound(dfn[x])!=q.begin()){
			auto w=*prev(q.lower_bound(dfn[x]));
			rs[bh]=*jl[w].begin();
			st.push_back({0,w,*jl[w].begin()});
			jl[w].erase(jl[w].begin());
			if(!jl[w].size())q.erase(q.find(w));
		}else if(q.upper_bound(eds[x])!=q.end()){
			auto w=*q.upper_bound(eds[x]);
			rs[bh]=*jl[w].begin();
			st.push_back({0,w,*jl[w].begin()});
			jl[w].erase(jl[w].begin());
			if(!jl[w].size())q.erase(q.find(w));
		}else{
			tot++;
			rs[bh]=tot;
			op=0;
		}
		if(a!=x)qs[up(a,dep[a]-dep[x]-1)].push_back({dfn[a],rs[bh]});
		if(b!=x)qs[up(b,dep[b]-dep[x]-1)].push_back({dfn[b],rs[bh]});
	    jl[dfn[x]].insert(rs[bh]);
	    q.insert(dfn[x]);
	    if(op)st.push_back({1,dfn[x],rs[bh]});
	}
	for(auto c:p[x]){
		if(mk[c])continue;
		int ls=st.size();
		for(auto [a,b]:qs[c]){
			jl[a].insert(b);
			st.push_back({1,a,b});
			q.insert(a);
			jl[dfn[x]].erase(jl[dfn[x]].find(b));
			if(!jl[dfn[x]].size())q.erase(q.find(dfn[x]));
			st.push_back({0,dfn[x],b});
		}
		solve(c);
		while(st.size()>ls)upt(st.back()),st.pop_back();
	}
	mk[x]=0;
	while(st.size()>lst)upt(st.back()),st.pop_back();
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>op>>t;
	while(t--){
		cin>>n>>m;
		idx=0;
		for(int i=1;i<=n;i++)p[i].clear(),g[i].clear(),qs[i].clear();
		for(int i=1;i<n;i++){
			int x,y;
			cin>>x>>y;
			p[x].push_back(y);
			p[y].push_back(x);
		}
		dfs(1);
		for(int i=1;i<=m;i++){
			int a,b;
			cin>>a>>b;
			int c=lca(a,b);
			g[c].push_back({a,b,i});
		}
		for(int i=1;i<=n;i++)jl[i].clear();
		tot=0;q.clear();st.clear();
		solve(1);
		cout<<tot<<"\n";
		for(int i=1;i<=m;i++)cout<<rs[i]<<" ";
		cout<<"\n";
	}
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 128ms

memory: 70292kb

input:

output:

result:

ok ok

Subtask #2:

score: 14

Accepted

Dependency #1:

100%

Accepted

Test #2:

score: 14

Accepted

time: 109ms

memory: 175052kb

input:

output:

result:

ok ok

Test #3:

score: 14

Accepted

time: 229ms

memory: 194168kb

input:

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 2 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 2 2 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: 112ms

memory: 115268kb

input:

output:

result:

ok ok

Test #5:

score: 14

Accepted

time: 133ms

memory: 113168kb

input:

output:

5
1 2 3 4 5 
4
1 4 4 2 3 
4
4 2 1 1 3 
4
1 1 2 3 4 
4
1 2 3 2 4 
3
3 2 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 2 1 
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: 62ms

memory: 71440kb

input:

output:

result:

ok ok

Test #7:

score: 14

Accepted

time: 69ms

memory: 70392kb

input:

output:

result:

ok ok

Test #8:

score: 14

Accepted

time: 128ms

memory: 118640kb

input:

output:

result:

ok ok

Test #9:

score: 14

Accepted

time: 153ms

memory: 114576kb

input:

output:

result:

ok ok

Test #10:

score: 14

Accepted

time: 244ms

memory: 172616kb

input:

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 3 1 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 2 2 3 ...

result:

ok ok

Subtask #3:

score: 9

Accepted

Test #11:

score: 9

Accepted

time: 528ms

memory: 314468kb

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

result:

ok ok

Test #12:

score: 9

Accepted

time: 441ms

memory: 140432kb

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
10823 9566 3751 11345 7703 6346 2007 5077 4808 5099 11330 7604 743 9097 8089 8628 226 4321 4857 3039 10107 5848 10823 6730 12284 1142 11142 12603 868 9084 3100 12549 5658 2123 11543 3526 334 7417 5695 4071 11803 760 6284 7372 12446 2790 1994 2278 6314 3350 7060 8685 10747 12569 8687 7280 7488 ...

result:

ok ok

Test #13:

score: 9

Accepted

time: 394ms

memory: 70576kb

input:

output:

160
123 62 126 55 79 150 115 11 145 156 59 19 46 28 68 119 140 18 1 118 142 60 2 133 85 5 54 129 7 26 13 57 105 4 79 96 48 81 32 38 99 50 24 108 106 1 116 76 72 47 37 18 24 36 81 14 144 3 61 51 112 125 65 57 16 32 77 52 21 8 76 47 148 25 84 131 31 3 113 132 44 109 81 50 18 42 40 87 7 122 97 9 93 39 ...

result:

ok ok

Test #14:

score: 9

Accepted

time: 400ms

memory: 71988kb

input:

output:

558
148 440 112 217 157 410 136 493 376 375 210 285 234 292 159 219 349 201 386 184 71 295 488 130 477 196 266 456 27 505 395 1 69 360 310 182 526 392 546 442 100 284 350 90 452 167 368 327 90 351 29 239 306 18 297 362 306 248 446 205 33 90 105 315 173 182 516 227 12 138 77 408 465 5 205 9 505 45 13...

result:

ok ok

Test #15:

score: 9

Accepted

time: 1229ms

memory: 332552kb

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
25705 1353 6008 28366 3385 22059 4847 11653 24683 5876 12409 17478 5830 11254 26212 6690 6837 20428 12162 7740 17852 9160 4426 6559 10158 4386 12022 11217 22473 17678 23118 15340 23853 19210 18109 26447 1733 8253 3664 7985 7121 5314 20432 12359 25764 11452 21068 15867 6727 12880 11561 7325 100...

result:

ok ok

Test #16:

score: 9

Accepted

time: 676ms

memory: 316784kb

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
37 158 105 50 32 61 24 89 47 166 130 173 153 115 58 32 104 6 72 101 74 19 165 48 4 64 20 4 96 177 113 85 11 169 12 144 111 21 82 20 26 40 16 52 70 44 81 32 42 111 78 116 146 86 46 99 117 87 15 57 75 137 30 15 97 43 118 45 14 16 26 58 21 147 106 171 17 60 49 10 100 18 5 83 76 119 54 95 7 67 77 16...

result:

ok ok

Subtask #4:

score: 20

Accepted

Test #17:

score: 20

Accepted

time: 8ms

memory: 69936kb

input:

output:

839
1 1 2 420 3 4 5 6 7 8 435 9 10 11 12 13 14 15 16 17 18 73 19 20 12 21 22 23 24 133 25 26 27 28 225 29 1 30 1 31 32 33 34 35 36 37 38 309 39 40 41 42 43 44 45 46 47 455 48 49 50 51 52 53 54 55 88 56 57 16 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 500 645 78 79 80 81 82 83 84 85 ...

result:

ok ok

Test #18:

score: 20

Accepted

time: 8ms

memory: 72332kb

input:

output:

417
153 97 233 397 333 69 121 49 90 76 336 246 283 88 55 197 11 60 224 21 243 49 154 3 117 258 354 173 324 8 92 36 198 17 167 318 210 367 199 22 65 213 239 252 323 178 44 49 54 241 60 229 32 242 45 108 146 18 220 29 204 100 128 97 113 31 366 280 52 49 352 24 12 1 398 50 358 174 168 155 56 315 278 92...

result:

ok ok

Test #19:

score: 20

Accepted

time: 13ms

memory: 69364kb

input:

output:

161
1 2 3 152 157 4 1 2 1 153 2 153 159 34 154 113 5 4 8 155 156 25 127 158 157 128 5 7 82 129 10 130 131 159 101 51 132 11 152 4 117 12 100 127 133 71 46 3 2 158 159 51 1 14 77 128 160 152 34 15 134 4 127 128 135 129 109 66 3 127 130 161 30 142 131 6 136 23 8 9 155 13 10 101 114 132 153 3 156 137 1...

result:

ok ok

Test #20:

score: 20

Accepted

time: 11ms

memory: 70732kb

input:

output:

473
270 36 22 241 471 69 254 56 170 276 288 22 241 272 168 293 307 353 419 359 158 169 77 272 382 287 67 337 38 130 334 347 275 63 375 16 135 115 63 40 383 326 209 172 117 410 130 54 145 60 183 198 123 324 317 80 196 25 351 131 212 250 387 226 96 363 315 237 210 192 250 186 125 317 401 341 211 146 1...

result:

ok ok

Test #21:

score: 20

Accepted

time: 11ms

memory: 70020kb

input:

output:

196
28 1 46 105 2 124 3 4 5 6 137 142 7 138 142 143 54 8 9 143 144 10 12 11 145 12 13 113 14 146 147 15 146 16 17 18 19 20 16 21 22 15 23 44 148 24 149 25 150 26 27 28 151 8 29 51 30 31 152 153 32 28 33 154 144 34 35 36 37 43 155 156 145 38 39 146 40 41 42 43 44 45 46 47 48 157 158 159 160 49 50 161...

result:

ok ok

Test #22:

score: 20

Accepted

time: 11ms

memory: 70668kb

input:

output:

216
1 14 2 122 4 3 122 103 99 101 118 4 104 5 6 7 105 8 9 10 11 12 13 14 9 108 54 109 45 15 65 82 37 110 112 16 89 123 38 17 18 159 160 114 130 161 19 8 115 117 20 72 21 96 147 22 27 85 23 84 24 25 26 27 12 28 124 29 24 47 125 30 31 32 33 34 35 36 37 38 39 40 126 41 127 128 129 42 43 136 152 46 130 ...

result:

ok ok

Test #23:

score: 20

Accepted

time: 15ms

memory: 69520kb

input:

output:

175
78 140 74 82 112 7 8 156 46 4 153 55 102 159 97 107 56 25 130 53 64 148 150 117 68 43 59 168 41 25 70 135 124 66 65 99 48 123 86 65 139 121 45 57 14 93 68 70 112 104 103 108 36 160 41 10 72 142 88 60 132 11 146 5 54 32 40 64 149 30 137 111 6 100 144 23 125 14 33 58 26 30 24 99 19 98 152 11 94 79...

result:

ok ok

Test #24:

score: 20

Accepted

time: 9ms

memory: 69424kb

input:

output:

588
89 467 468 469 467 470 1 2 3 371 4 5 6 468 7 126 8 14 471 9 10 472 11 12 13 14 473 15 16 30 469 17 470 471 18 19 472 474 20 21 200 47 347 22 23 24 25 473 8 26 27 28 29 30 31 32 474 33 475 150 59 476 34 477 478 35 475 360 36 479 37 38 39 480 40 41 42 43 44 45 46 47 481 48 476 49 288 477 50 51 282...

result:

ok ok

Test #25:

score: 20

Accepted

time: 12ms

memory: 70972kb

input:

output:

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

result:

ok ok

Test #26:

score: 20

Accepted

time: 15ms

memory: 71148kb

input:

output:

648
1 3 2 3 4 5 8 170 9 6 7 8 5 9 10 10 11 11 12 30 13 14 15 16 89 33 30 17 18 19 15 20 21 490 40 22 23 18 24 25 26 27 28 29 30 31 32 33 34 35 68 36 23 89 37 38 27 39 38 40 204 28 41 42 43 77 44 45 68 46 93 75 47 31 163 32 48 49 111 50 51 52 76 53 46 77 48 54 87 55 56 5 93 50 57 15 58 94 59 100 55 1...

result:

ok ok

Test #27:

score: 20

Accepted

time: 14ms

memory: 70124kb

input:

output:

675
79 21 88 90 88 89 101 102 103 136 90 391 101 147 224 149 219 153 162 91 92 588 93 94 103 282 136 1 95 96 97 163 98 180 99 100 101 204 215 102 204 240 244 103 104 248 73 105 106 291 107 108 109 309 326 215 41 370 375 110 395 291 111 112 113 114 115 378 2 106 116 402 3 4 117 404 118 119 5 120 12 4...

result:

ok ok

Test #28:

score: 20

Accepted

time: 14ms

memory: 69896kb

input:

output:

377
13 36 1 44 208 2 3 41 4 126 136 51 5 35 131 56 109 6 7 8 9 32 10 11 12 139 13 79 14 98 7 15 243 16 17 18 19 124 145 20 130 21 22 23 24 25 26 1 27 122 190 207 100 208 172 28 29 30 212 213 244 31 216 224 245 32 89 33 227 233 194 235 34 243 244 245 62 35 36 37 246 38 129 76 115 39 40 247 5 181 248 ...

result:

ok ok

Test #29:

score: 20

Accepted

time: 16ms

memory: 72448kb

input:

output:

261
243 1 2 3 4 5 6 7 8 9 6 10 11 12 13 14 15 16 17 18 19 20 21 252 22 23 184 24 187 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 239 154 55 56 57 58 59 5 60 61 62 63 64 65 66 67 106 68 69 70 71 198 223 72 73 74 75 76 77 78 79 80 146 81 82 83 84 85 86 87 ...

result:

ok ok

Test #30:

score: 20

Accepted

time: 19ms

memory: 70184kb

input:

output:

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

result:

ok ok

Test #31:

score: 20

Accepted

time: 15ms

memory: 69336kb

input:

output:

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

result:

ok ok

Test #32:

score: 20

Accepted

time: 19ms

memory: 69436kb

input:

output:

150
4 1 2 2 2 3 1 4 3 4 4 1 5 7 3 6 6 7 6 5 1 6 6 4 2 7 8 8 9 8 10 9 2 14 11 3 5 9 12 4 2 4 10 9 13 6 72 10 2 35 11 11 2 9 5 6 12 14 4 7 7 8 11 9 106 15 3 14 10 12 8 11 20 11 9 10 13 12 13 3 11 14 15 16 12 1 15 12 13 14 16 19 4 14 17 6 17 18 13 16 19 14 14 21 15 22 20 15 16 16 17 56 18 17 18 17 19 7...

result:

ok ok

Subtask #5:

score: 22

Accepted

Dependency #4:

100%

Accepted

Test #33:

score: 22

Accepted

time: 187ms

memory: 98616kb

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
1 2 3 4 2561 18715 5 1670 6 7 8 9 10 11 12 13 14 15 16 1362 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 15003 40 41 1274 42 43 44 45 46 489 47 48 2469 49 50 51 52 53 54 55 56 57 58 59 60 61 62 137 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 ...

result:

ok ok

Test #34:

score: 22

Accepted

time: 197ms

memory: 101912kb

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
7900 1 2 3 23 34 4 135 5 6539 235 264 6 285 23 1 292 313 373 7 384 16248 8 15975 389 15953 9 415 19041 436 439 10 10859 11 450 273 493 11537 12 496 13 34 499 547 6773 15424 14 15 559 436 16 578 598 605 17 14126 26836 18 626 19 20 21 22 4627 651 656 665 8067 679 15901 18482 23 24 496 8421 25 11...

result:

ok ok

Test #35:

score: 22

Accepted

time: 168ms

memory: 106656kb

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
1 39857 2 3 39858 39857 39859 37389 4 5 39858 6 7 8 39859 39860 9 10 11 45067 12 56213 26528 7191 39861 13 14 15 39860 39862 16 17 18 19 20 12624 11545 21 415 32768 39863 39864 39865 22 23 24 41382 25 39866 26 39861 39867 27 28 29 30 39868 39869 33642 33025 31 2157 20753 32 39870 39871 12407 3...

result:

ok ok

Test #36:

score: 22

Accepted

time: 98ms

memory: 79964kb

input:

output:

11000
1 2 3 4 1965 5 6 2733 7 8 9 10 11 12 1955 13 14 895 15 438 16 17 18 19 20 21 22 23 24 25 26 4255 27 28 7346 29 30 31 32 8814 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 4244 58 1131 59 60 61 62 4206 63 64 65 66 67 68 69 70 71 615 72 73 74 75 76 77 78 79 80 81 82 ...

result:

ok ok

Test #37:

score: 22

Accepted

time: 107ms

memory: 80148kb

input:

output:

3386
1 2 5 3 4 5 6 6 7 8 16 20 21 30 16 9 10 16 11 60 12 64 13 14 1 66 20 15 83 16 17 18 249 103 19 104 107 20 21 22 109 3 23 24 25 26 21 110 27 28 29 101 30 31 113 120 32 33 34 125 22 6 35 36 37 38 39 40 154 41 42 7 158 172 43 188 198 44 211 45 46 1775 41 47 48 35 94 49 50 51 215 218 52 220 222 53 ...

result:

ok ok

Test #38:

score: 22

Accepted

time: 112ms

memory: 80540kb

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
6 14 1 153 1 1025 34 2 3 54 73 97 209 4 309 106 131 133 137 2 5 4 150 169 1026 198 7 201 6 137 316 206 7 209 212 8 214 258 9 10 214 10 263 11 11 329 309 12 337 340 13 316 14 316 12 133 155 158 93 3 342 7 13 9 13 15 62 111 344 5 6 8 7 713 41 43 50 1027 10 52 15 1028 3 301 16 1 5 64 13 329 1025 1...

result:

ok ok

Test #39:

score: 22

Accepted

time: 108ms

memory: 71172kb

input:

output:

451
1 5 5 2 5 15 15 36 36 3 38 38 51 51 67 4 67 83 83 5 85 5 88 85 90 6 95 7 123 131 88 134 90 95 123 8 157 161 131 175 184 191 192 193 134 194 195 196 9 157 197 175 10 184 9 198 199 36 191 200 192 3 11 5 12 1 193 201 202 203 204 13 14 15 16 17 205 206 38 207 208 18 19 209 194 195 210 20 196 197 8 8...

result:

ok ok

Test #40:

score: 22

Accepted

time: 100ms

memory: 72540kb

input:

output:

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

result:

ok ok

Test #41:

score: 22

Accepted

time: 105ms

memory: 71144kb

input:

output:

345
323 164 168 168 145 100 26 88 116 108 207 247 241 271 339 314 130 3 123 122 272 273 128 263 55 269 182 140 266 234 307 109 305 18 143 52 230 133 156 136 298 15 127 148 172 154 225 284 23 44 216 35 203 87 81 223 130 51 84 6 57 88 181 293 199 289 134 106 74 108 15 174 42 290 229 152 308 171 194 7 ...

result:

ok ok

Test #42:

score: 22

Accepted

time: 105ms

memory: 71432kb

input:

output:

695
1 307 2 3 525 341 526 258 382 527 4 528 430 365 5 51 89 6 529 7 383 530 531 532 268 353 525 533 301 288 534 384 8 578 44 382 203 526 383 45 9 561 527 10 384 535 11 536 385 12 58 537 538 528 385 529 530 386 387 13 539 540 690 386 531 204 14 541 61 542 266 532 533 544 337 543 173 544 387 15 207 28...

result:

ok ok

Test #43:

score: 22

Accepted

time: 212ms

memory: 119208kb

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
24873 1493 18933 16293 2446 1378 12727 15942 10823 25502 15971 7316 14309 45801 6595 13713 28675 44033 3447 9495 26767 22714 28466 20743 5833 27708 8894 5243 20578 19939 19473 7025 8281 13532 133 37706 32690 18021 29669 20024 14781 26067 3306 34844 46596 47413 7058 45500 28840 4407 14100 3716 ...

result:

ok ok

Test #44:

score: 22

Accepted

time: 132ms

memory: 99808kb

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
1 40 1 2 3 4 5 26 6 7 8 9 1 10 11 12 49 13 14 15 125 38 16 17 18 4 16 19 20 21 22 23 51 24 25 26 27 28 5 29 30 31 80 32 33 34 35 4 2 36 37 3 38 31 39 40 5 41 42 43 44 45 46 6 47 48 49 50 51 10 52 53 7 6 83 54 55 56 57 58 11 59 60 61 62 63 64 65 9 8 66 67 68 69 70 71 72 73 74 75 76 112 77 96 78 7...

result:

ok ok

Test #45:

score: 22

Accepted

time: 138ms

memory: 102508kb

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
9979 1 2 9980 3 4 5 6 7 9981 4 9982 9983 1 4 1 10002 6 7 8 7 1 8 7 10002 8 9 8 8 9984 9985 9 10003 10004 10 10 9 10 9 11 10005 6 9 10 11 12 11 9986 12 12 8 9987 10006 9 10 10007 11 13 13 9988 13 12 14 10 15 11 12 14 16 15 11 9989 16 12 10003 14 17 10008 17 10009 18 13 13 10004 14 10010 10011 9...

result:

ok ok

Test #46:

score: 22

Accepted

time: 176ms

memory: 120824kb

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
5699 3128 7847 16742 16644 20630 30247 11040 7663 5593 9864 19338 30394 5345 22261 14936 5158 2323 8978 28698 19727 24012 17356 12029 16338 20233 21472 18455 29700 9449 21908 23298 17934 13680 15117 12549 14901 14594 19584 11665 5105 15118 4727 11811 12039 6500 13846 2020 7902 1331 10155 20857...

result:

ok ok

Test #47:

score: 22

Accepted

time: 98ms

memory: 79844kb

input:

output:

4114
1 2 3 4 5 6 7 5 8 9 10 11 12 6 13 14 15 9 16 17 18 1 19 20 21 22 23 24 25 2 9 26 2 27 28 29 30 12 31 32 33 34 1 35 154 4 36 37 27 3 38 39 3 40 41 12 13 42 43 44 45 46 79 47 48 49 50 51 52 53 54 55 56 43 57 4 58 59 60 61 62 7 14 63 64 65 19 23 24 8 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81...

result:

ok ok

Test #48:

score: 22

Accepted

time: 122ms

memory: 83984kb

input:

output:

2862
2368 1649 2189 988 356 788 420 876 1250 1855 1526 1797 758 1469 842 608 357 2294 418 1133 430 1875 563 72 299 1034 2314 1897 705 1383 2084 585 813 16 799 445 788 2833 1221 427 1290 1585 120 1076 1038 1951 410 1851 137 393 2543 2194 1576 27 2601 852 929 1855 384 1701 2841 2050 2691 1958 1587 187...

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: 501ms

memory: 319060kb

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
18 17 49 90 59 27 31 1 48 62 68 59 26 51 62 6 69 88 74 83 29 80 8 30 47 82 63 98 20 10 106 25 17 58 91 95 29 34 14 53 94 57 6 29 34 40 72 79 9 37 36 75 51 93 102 71 32 2 2 7 66 105 38 20 85 16 92 2 48 65 96 5 84 59 35 64 8 50 14 84 12 76 53 69 70 4 23 102 90 67 27 24 39 97 42 70 18 42 21 78 16 7...

result:

ok ok

Test #50:

score: 32

Accepted

time: 1613ms

memory: 325204kb

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
31356 64071 111264 172334 45975 15337 182973 229823 88553 91983 37255 4463 216481 114130 32125 136250 59526 147317 4334 148386 105359 51303 130548 40204 86116 3311 37389 184688 59462 175158 124118 93229 58929 128292 32395 83963 186060 27424 85851 3563 7100 13046 57341 109482 3680 145206 22489...

result:

ok ok

Test #51:

score: 32

Accepted

time: 1389ms

memory: 216012kb

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
1 2 3 4 5 6 7 48476 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2303 27 28 29 30 31 32 33 2272 34 5136 35 36 37 38 39 40 41 42 16743 43 44 45 74801 46 68159 47 48 49 50 51 194301 52 53 54 55 56 57 58 59 60 61 62 3569 63 64 137404 318092 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 ...

result:

ok ok

Test #52:

score: 32

Accepted

time: 795ms

memory: 122640kb

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
1447 10703 1 2 28738 28795 29583 3 29609 5234 4 30166 30263 30521 5 450 30738 16603 30766 1535 6 7 8 30767 9 30768 1557 10 30774 30781 1976 30786 30787 30788 30793 30 30797 30800 11 31001 12 30802 2232 13 30805 30807 30808 54 14 30816 6019 374 30817 30822 30823 30824 30826 30829 20036 30835 15...

result:

ok ok

Test #53:

score: 32

Accepted

time: 813ms

memory: 169720kb

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
1 2 3 4069 3679 1806 4554 199 7428 132 2052 5030 2175 5321 4 231 6163 5966 3589 2760 4818 1406 3096 5553 8064 3364 1350 2706 5 3331 3732 1236 1675 4412 3885 7637 4753 6 591 6663 7 8 484 5216 9 7327 262 2734 488 617 662 4180 3091 10 6067 6386 5929 3753 2302 2155 2891 1475 404 7293 259 5247 5594 ...

result:

ok ok

Test #54:

score: 32

Accepted

time: 699ms

memory: 156728kb

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 46386 11681 9383 38544 17424 25244 54885 46903 7155 28762 12738 21208 6426 9341 27742 18438 36632 14387 4974 26663 25261 4611 34377 31877 15497 38492 43384 47240 38715 49312 27590 19170 25600 41270 6135 2611 45314 41927 58992 3166 1166 53939 35355 40486 25236 60576 36090 39356 8665 45641...

result:

ok ok

Test #55:

score: 32

Accepted

time: 468ms

memory: 72272kb

input:

output:

604
1 2 478 3 2 3 4 50 483 321 5 1 483 6 432 7 484 485 486 484 485 8 9 3 10 2 11 487 12 445 13 14 15 488 16 5 17 75 1 5 4 18 483 489 490 491 19 492 493 13 18 102 124 494 56 283 495 496 20 21 198 486 22 487 497 498 530 239 23 24 25 26 50 27 499 28 484 488 500 29 322 489 30 501 165 502 503 286 321 31 ...

result:

ok ok

Test #56:

score: 32

Accepted

time: 505ms

memory: 71684kb

input:

output:

1521
1 2 3 1143 4 5 6 1093 257 7 8 651 562 9 1094 10 11 12 13 859 1179 1095 14 1096 15 795 1097 1094 546 1326 197 16 17 18 162 1095 1096 313 19 20 1512 21 22 1097 23 24 1098 25 210 26 624 1098 27 1099 28 29 1174 30 806 349 31 32 33 511 49 268 34 1100 1351 35 840 874 889 1099 1101 1083 36 1100 37 243...

result:

ok ok

Test #57:

score: 32

Accepted

time: 477ms

memory: 72412kb

input:

output:

747
588 1 2 588 3 4 5 589 590 374 589 590 591 591 592 6 7 8 592 501 9 317 593 10 594 593 11 12 13 595 14 594 15 16 596 380 137 597 17 18 19 20 21 227 331 22 595 608 23 706 24 25 596 579 597 598 580 26 598 317 27 391 28 29 599 576 318 30 599 31 32 33 255 600 34 35 39 36 37 38 442 421 39 40 41 42 43 4...

result:

ok ok

Test #58:

score: 32

Accepted

time: 487ms

memory: 71820kb

input:

output:

344
5 2 1 2 3 4 6 5 7 6 10 7 8 9 15 10 130 11 12 13 14 15 17 5 23 16 17 18 19 29 56 20 21 44 46 22 52 23 24 70 72 25 86 91 26 27 28 93 29 97 30 31 32 33 34 35 36 108 109 37 38 120 39 40 41 128 8 143 144 145 146 135 42 43 44 147 148 149 150 45 151 152 2 121 46 47 48 153 154 1 49 50 51 35 52 53 54 55 ...

result:

ok ok

Test #59:

score: 32

Accepted

time: 500ms

memory: 75212kb

input:

output:

730
1 2 37 49 3 4 5 6 7 8 212 275 331 9 55 10 11 50 104 12 41 13 302 27 319 19 175 14 15 19 16 93 103 32 398 33 32 155 17 18 104 35 19 20 21 55 79 12 22 19 6 23 20 24 77 10 714 143 386 108 47 104 5 40 110 39 389 25 26 5 399 153 27 28 59 6 46 29 153 4 243 30 110 21 283 31 79 27 67 8 10 74 320 76 252 ...

result:

ok ok

Test #60:

score: 32

Accepted

time: 1772ms

memory: 325756kb

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
91426 159214 74324 116335 156817 161626 25375 5196 15127 105051 39453 124543 69261 63527 172614 106789 42674 35278 51902 93651 69498 84332 131589 169765 71900 64267 88958 34142 30000 55183 92366 68013 24297 118286 148420 30356 146831 85991 181170 9399 174490 10189 109010 989 93748 65908 82328...

result:

ok ok