QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#447803	#8359. travel	grass8cow	100 ✓	289ms	175776kb	C++17	5.0kb	2024-06-18 20:05:51	2024-06-18 20:05:53

Judging History

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

[2024-06-18 20:05:53]
评测

测评结果：100
用时：289ms
内存：175776kb

查看

[2024-06-18 20:05:51]
提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
#define pp pop_back
int n;ll k;
vector<int>g[1010000];
namespace case_xiao{
	int MX,rt;
	void dfs1(int x,int f,int d){
		if(d>MX)MX=d,rt=x;
		for(int v:g[x])if(v!=f)dfs1(v,x,d+1);
	}
	int fa[501000],d[501000],V,p[501000],R;
	bool oe[501000];
	int dis(int a,int b){
		while(a!=b){if(d[a]<d[b])swap(a,b);a=fa[a];}
		return d[a];
	}
	int pd(int a,int b){
		return d[a]+d[b]-dis(a,b)*2;
	}
	void dfs(int x){for(int v:g[x])if(v!=fa[x])d[v]=d[x]+1,fa[v]=x,dfs(v);}
	void df(int x){p[++R]=x;for(int v:g[x])if(v!=fa[x])df(v);}
	void print(int x){
		if(x!=V)p[++R]=x;
		for(int v:g[x])if(v!=fa[x]&&!oe[v])df(v);
		for(int v:g[x])if(v!=fa[x]&&oe[v])print(v);
	}
	void sol(){
		R=0;
		MX=-1,rt=0,dfs1(1,0,0);
		for(int i=1;i<=n;i++)fa[i]=d[i]=0,oe[i]=0;
		dfs(rt);
		MX=0;
		for(int i=1;i<=n;i++)MX=max(MX,d[i]);
		k=(n-1)*2-k;
		if(k>MX){puts("-1");return;}
		V=0;for(int i=1;i<=n;i++)if(d[i]==k)V=i;
		int V_=V;
		while(V_)oe[V_]=1,V_=fa[V_];
		print(rt),p[++R]=V;
		for(int i=1;i<=n;i++)printf("%d ",p[i]);
		puts("");
	}
}
int sz[1010000],rt,MX;
void dfs1(int x,int f){
	sz[x]=1;int mm=-1;
	for(int v:g[x])if(v!=f)dfs1(v,x),sz[x]+=sz[v],mm=max(mm,sz[v]);
	mm=max(mm,n-sz[x]);
	if(MX>mm)MX=mm,rt=x;
}
int d[1010000],le[1010000],fa[1010000];
vector<int>vc,cv;
int be[501000];
void dfs(int x){
	sz[x]=1,le[x]=0;
	for(int v:g[x])if(v!=fa[x]){
		fa[v]=x,d[v]=d[x]+1,dfs(v),sz[x]+=sz[v];
		if(!le[x])le[x]=le[v];
	}
	if(sz[x]==1)vc.pb(x),le[x]=x;
	else cv.pb(x);
}
int dis(int a,int b){
	while(a!=b){if(d[a]<d[b])swap(a,b);a=fa[a];}
	return d[a];
}
int pd(int a,int b){
	return d[a]+d[b]-dis(a,b)*2;
}
vector<int>Q[501000],E[500100];
#define pi pair<int,int>
#define F first
#define S second
#define mp make_pair
vector<pi>M[501000];int M_[501000];
struct qq{int dt,u,v;};
vector<qq>Z[501000];
int pr[501000],nx[501000];bool vis[500100];
void Op(qq x){
	int u=x.u,v=x.v;
	if(v)pr[v]=u,nx[u]=v;
	else Q[le[u]].pb(u),vis[u]=1;
}
int pv[501000],nv[501000];
int sta[500100],top;
void getcol(){
	top=0;priority_queue<pi>q;
	for(int v:g[rt])q.push(mp(M[v].size()+1,v));
	while(!q.empty()){
		pi a=q.top();q.pop();
		if(a.S!=sta[top]){
			sta[++top]=a.S;
			if(a.F>1)q.push(mp(a.F-1,a.S));
		}
		else{
			pi b=q.top();q.pop();
			sta[++top]=b.S;
			if(b.F>1)q.push(mp(b.F-1,b.S));
			q.push(a);
		}
	}
}
int p[501000],R;
void step1(){
	MX=n+1,rt=0,dfs1(1,0),fa[rt]=0,d[rt]=0;
	for(int v:g[rt]){
		d[v]=1,fa[v]=rt,vc.clear(),cv.clear(),dfs(v);
		if(sz[v]==1){be[v]=v;continue;}
		int pt=-1;
		for(int i:vc){be[i]=v;if(pt!=-1)Z[v].pb((qq){dis(i,pt),pt,i});pt=i;}
		for(int i:cv)Z[v].pb((qq){d[i],i,0}),be[i]=v;
		sort(Z[v].begin(),Z[v].end(),[&](qq x,qq y){return x.dt<y.dt;});
		E[(int)Z[v].size()].pb(v);
	}
}
void Zk(int u){while(u)p[++R]=u,u=nv[u];}
void sol(){
	int op;
	scanf("%d%lld%d",&n,&k,&op);
	for(int i=0;i<=n;i++)pv[i]=nv[i]=pr[i]=nx[i]=be[i]=0,g[i].clear(),Q[i].clear(),Z[i].clear(),fa[i]=d[i]=le[i]=sz[i]=0,E[i].clear(),vis[i]=0,M[i].clear();
	if(n==1){if(k)puts("-1");else puts("1");return;}
	if(n==2){if(k!=op)puts("-1");else puts("1 2");return;}
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].pb(v),g[v].pb(u);
	if(k<(n-1)*2){
		if(op==1){case_xiao::sol();return;}
		puts("-1");return;
	}
	step1();//取出可能的减k方式
	ll dg=0;for(int i=1;i<=n;i++)if(i!=rt)dg+=sz[i];
	if(op==2&&(dg*2<k||(k&1))){puts("-1");return;} 
	if(op==1&&dg*2<=k){puts("-1");return;}
	int zk=(k%2);if(op==1)k+=2-zk;
	k=(dg*2-k)/2;
	int mg=n;
	while(k){
		while(E[mg].empty())mg--;
		int u=E[mg].back();E[mg].pp(),E[mg-1].pb(u);
		if(k>Z[u].back().dt)Op(Z[u].back()),k-=Z[u].back().dt,Z[u].pp();
		else{
			for(qq jz:Z[u])if(jz.dt==k){Op(jz);break;}
			k=0;
		}
	}
	int tg=0;
	for(int i=1;i<=n;i++)if(i!=rt){
		if(sz[i]==1){
			if(pr[i])continue;
			int o=i,ls=0,fi=0;
			while(o){
				tg++;
				sort(Q[o].begin(),Q[o].end(),[&](int x,int y){return d[x]<d[y];});
				for(int u:Q[o]){
					tg++;
					if(!fi)fi=u;
					else pv[u]=ls,nv[ls]=u;
					ls=u;
				}
				if(!fi)fi=o;else pv[o]=ls,nv[ls]=o;ls=o;
				o=nx[o];
			}
			if(fi!=be[i])M[be[i]].pb(mp(fi,ls));
			else M_[be[i]]=ls;
			continue;
		}
		if(vis[i])continue;
		tg++;
		if(i!=be[i])M[be[i]].pb(mp(i,i));
		else M_[i]=i;
	}
	getcol();
	R=0;
	if(zk){
		for(int v:g[rt])M[v].pb(mp(v,M_[v]));
		for(int i=1;i<=top;i++){pi e=M[sta[i]].back();M[sta[i]].pp();Zk(e.F);}
		p[++R]=rt;
	}
	else{
		int xp=-1;
		for(int i=1;i<top;i++)if(sta[i]!=sta[i+1]){xp=i;break;}
		assert(xp!=-1);
		Zk(sta[xp+1]);
		for(int i=xp+2;i<=top;i++){
			int o=sta[i];
			if(!M[o].empty())Zk(M[o].back().F),M[o].pp();
			else Zk(o);
		}
		p[++R]=rt;
		for(int i=1;i<xp;i++){
			int o=sta[i];
			if(!M[o].empty())Zk(M[o].back().F),M[o].pp();
			else Zk(o);
		}
		int u=M_[sta[xp]];
		while(u)p[++R]=u,u=pv[u];
	}
	for(int i=1;i<=n;i++)printf("%d ",p[i]);puts("");
}
int main(){
	int T;cin>>T;while(T--)sol();
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2

Accepted

Test #1:

score: 2

Accepted

time: 10ms

memory: 81464kb

input:

output:

result:

ok Accepted.

Subtask #2:

score: 4

Accepted

Test #2:

score: 4

Accepted

time: 8ms

memory: 103700kb

input:

output:

3 9 4 8 7 1 6 2 5 
7 6 3 1 5 8 4 2 9 
7 5 9 2 1 6 4 3 8 
6 4 2 8 7 1 3 9 5 
7 2 9 8 6 5 4 3 1

result:

ok Accepted.

Test #3:

score: 4

Accepted

time: 15ms

memory: 104920kb

input:

output:

5 9 3 4 1 2 8 7 6 
6 7 8 9 2 3 4 5 1 
8 9 2 1 4 6 5 7 3 
3 2 6 5 1 4 9 7 8 
8 7 3 2 9 4 1 6 5

result:

ok Accepted.

Test #4:

score: 4

Accepted

time: 4ms

memory: 102484kb

input:

output:

4 7 8 2 3 9 1 6 5 
4 3 7 2 6 9 1 5 8 
4 3 2 7 1 6 5 9 8 
4 3 7 1 2 5 8 6 9 
3 8 4 6 7 2 9 1 5

result:

ok Accepted.

Test #5:

score: 4

Accepted

time: 4ms

memory: 103928kb

input:

output:

2 9 8 5 7 6 4 3 1 
8 7 5 1 4 3 2 6 9 
2 8 9 7 4 6 1 5 3 
8 6 3 1 4 5 2 7 9 
9 8 7 4 6 1 2 5 3

result:

ok Accepted.

Test #6:

score: 4

Accepted

time: 7ms

memory: 97496kb

input:

output:

1 5 6 2 8 3 7 9 4 
7 8 4 3 6 2 1 5 9 
9 8 4 2 5 3 1 7 6 
7 9 8 5 3 1 2 6 4 
7 9 3 4 2 1 5 8 6

result:

ok Accepted.

Test #7:

score: 4

Accepted

time: 12ms

memory: 102736kb

input:

output:

6 9 7 8 5 4 2 3 1 
-1
-1
6 4 9 7 8 1 3 2 5 
-1

result:

ok Accepted.

Test #8:

score: 4

Accepted

time: 7ms

memory: 95224kb

input:

output:

result:

ok Accepted.

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #9:

score: 8

Accepted

time: 8ms

memory: 103744kb

input:

output:

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

result:

ok Accepted.

Test #10:

score: 8

Accepted

time: 8ms

memory: 102824kb

input:

output:

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

result:

ok Accepted.

Test #11:

score: 8

Accepted

time: 4ms

memory: 97156kb

input:

output:

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

result:

ok Accepted.

Test #12:

score: 8

Accepted

time: 12ms

memory: 98096kb

input:

output:

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

result:

ok Accepted.

Test #13:

score: 8

Accepted

time: 7ms

memory: 97660kb

input:

output:

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

result:

ok Accepted.

Test #14:

score: 8

Accepted

time: 8ms

memory: 102856kb

input:

output:

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

result:

ok Accepted.

Test #15:

score: 8

Accepted

time: 9ms

memory: 94780kb

input:

output:

result:

ok Accepted.

Subtask #4:

score: 14

Accepted

Test #16:

score: 14

Accepted

time: 12ms

memory: 104488kb

input:

output:

4 9 3 8 2 7 1 5 6 
4 2 1 8 9 3 7 5 6 
5 9 10 4 8 3 2 1 6 7 
4 8 9 2 7 3 1 5 6 
7 9 10 4 8 3 2 1 6 5 
7 5 10 4 9 3 8 2 1 6 
5 10 3 9 2 8 4 1 6 7 
5 4 3 2 1 8 9 10 6 7 
4 8 9 2 7 3 1 5 6 
10 9 8 7 6 5 4 2 1 3 
5 7 4 8 9 10 3 2 1 6 
7 5 4 3 2 1 8 9 10 6 
5 10 4 9 3 8 2 1 6 7 
6 3 7 9 2 8 1 5 4 
5 2 1 1...

result:

ok Accepted.

Test #17:

score: 14

Accepted

time: 4ms

memory: 104500kb

input:

output:

9 8 7 6 5 4 3 2 1 
4 6 7 8 9 3 2 1 5 
9 8 7 6 5 4 3 2 1 
-1
6 4 8 9 2 7 3 1 5 
-1
-1
4 3 2 1 5 9 8 7 6 
-1
-1
-1
-1
-1
-1
6 4 9 3 8 2 7 1 5 
-1
-1
-1
-1
-1
-1
-1
-1
-1
9 8 7 6 5 4 3 2 1 
-1
-1
-1
-1
-1
-1
10 9 8 7 6 5 4 3 2 1 
-1
9 8 7 6 5 4 3 2 1 
-1
6 4 1 8 9 3 7 2 5 
-1
-1
5 10 4 9 3 2 1 8 6 7 
-...

result:

ok Accepted.

Test #18:

score: 14

Accepted

time: 7ms

memory: 95284kb

input:

output:

result:

ok Accepted.

Test #19:

score: 14

Accepted

time: 8ms

memory: 104376kb

input:

output:

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

result:

ok Accepted.

Test #20:

score: 14

Accepted

time: 8ms

memory: 103900kb

input:

output:

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

result:

ok Accepted.

Test #21:

score: 14

Accepted

time: 4ms

memory: 104204kb

input:

output:

384 383 382 381 380 379 378 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 ...

result:

ok Accepted.

Test #22:

score: 14

Accepted

time: 4ms

memory: 104312kb

input:

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

output:

189 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 ...

result:

ok Accepted.

Test #23:

score: 14

Accepted

time: 4ms

memory: 98540kb

input:

1
1934 290581 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
5...

output:

969 967 1251 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 14...

result:

ok Accepted.

Test #24:

score: 14

Accepted

time: 14ms

memory: 99232kb

input:

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

output:

959 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 10...

result:

ok Accepted.

Test #25:

score: 14

Accepted

time: 11ms

memory: 101412kb

input:

1
1835 1628390 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
...

output:

917 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 916 1819 915 1818 914 1817 913 1816 912 1815 911 1814 910 1813 909 1812 908 1811 907 1810 906 1809 905 1808 904 1807 903 1806 902 1805 901 1804 900 1803 899 1802 898 1801 897 1800 896 1799 895 1798 894 1797 893 1796 ...

result:

ok Accepted.

Test #26:

score: 14

Accepted

time: 4ms

memory: 98036kb

input:

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

output:

927 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1...

result:

ok Accepted.

Subtask #5:

score: 10

Accepted

Dependency #4:

100%

Accepted

Test #27:

score: 10

Accepted

time: 81ms

memory: 95864kb

input:

output:

result:

ok Accepted.

Test #28:

score: 10

Accepted

time: 110ms

memory: 118392kb

input:

5
93044 1765038246 2
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:

46522 66879 76230 76231 76232 76233 76234 76235 76236 76237 76238 76239 76240 76241 76242 76243 76244 76245 76246 76247 76248 76249 76250 76251 76252 76253 76254 76255 76256 76257 76258 76259 76260 76261 76262 76263 76264 76265 76266 76267 76268 76269 76270 76271 76272 76273 76274 76275 76276 76277 ...

result:

ok Accepted.

Test #29:

score: 10

Accepted

time: 157ms

memory: 174760kb

input:

1
481849 965190 2
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:

240926 240923 240934 240953 240954 240955 240956 240957 240958 240959 240960 240961 240962 240963 240964 240965 240966 240967 240968 240969 240970 240971 240972 240973 240974 240975 240976 240977 240978 240979 240980 240981 240982 240983 240984 240985 240986 240987 240988 240989 240990 240991 240992...

result:

ok Accepted.

Test #30:

score: 10

Accepted

time: 133ms

memory: 175776kb

input:

1
494761 38887392602 2
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
...

output:

247380 386820 386821 386822 386823 386824 386825 386826 386827 386828 386829 386830 386831 386832 386833 386834 386835 386836 386837 386838 386839 386840 386841 386842 386843 386844 386845 386846 386847 386848 386849 386850 386851 386852 386853 386854 386855 386856 386857 386858 386859 386860 386861...

result:

ok Accepted.

Test #31:

score: 10

Accepted

time: 120ms

memory: 174700kb

input:

1
490645 44453587331 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
...

output:

245324 245322 394408 394409 394410 394411 394412 394413 394414 394415 394416 394417 394418 394419 394420 394421 394422 394423 394424 394425 394426 394427 394428 394429 394430 394431 394432 394433 394434 394435 394436 394437 394438 394439 394440 394441 394442 394443 394444 394445 394446 394447 394448...

result:

ok Accepted.

Test #32:

score: 10

Accepted

time: 123ms

memory: 168612kb

input:

1
456012 71620971179 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
...

output:

228006 228008 228005 272888 417243 417244 417245 417246 417247 417248 417249 417250 417251 417252 417253 417254 417255 417256 417257 417258 417259 417260 417261 417262 417263 417264 417265 417266 417267 417268 417269 417270 417271 417272 417273 417274 417275 417276 417277 417278 417279 417280 417281...

result:

ok Accepted.

Test #33:

score: 10

Accepted

time: 57ms

memory: 104500kb

input:

output:

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

result:

ok Accepted.

Test #34:

score: 10

Accepted

time: 85ms

memory: 104660kb

input:

output:

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

result:

ok Accepted.

Test #35:

score: 10

Accepted

time: 83ms

memory: 104304kb

input:

output:

117 115 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 113 163 112 162 111 ...

result:

ok Accepted.

Test #36:

score: 10

Accepted

time: 86ms

memory: 106884kb

input:

200
2422 1517004 2
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:

1211 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 ...

result:

ok Accepted.

Test #37:

score: 10

Accepted

time: 104ms

memory: 111248kb

input:

50
9167 6418302 2
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:

4583 5120 6374 6375 6376 6377 6378 6379 6380 6381 6382 6383 6384 6385 6386 6387 6388 6389 6390 6391 6392 6393 6394 6395 6396 6397 6398 6399 6400 6401 6402 6403 6404 6405 6406 6407 6408 6409 6410 6411 6412 6413 6414 6415 6416 6417 6418 6419 6420 6421 6422 6423 6424 6425 6426 6427 6428 6429 6430 6431 ...

result:

ok Accepted.

Test #38:

score: 10

Accepted

time: 90ms

memory: 115012kb

input:

20
24105 203761007 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...

output:

12054 12052 22146 22147 22148 22149 22150 22151 22152 22153 22154 22155 22156 22157 22158 22159 22160 22161 22162 22163 22164 22165 22166 22167 22168 22169 22170 22171 22172 22173 22174 22175 22176 22177 22178 22179 22180 22181 22182 22183 22184 22185 22186 22187 22188 22189 22190 22191 22192 22193 ...

result:

ok Accepted.

Test #39:

score: 10

Accepted

time: 117ms

memory: 112832kb

input:

10
48337 97528 2
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:

24168 24190 24191 24192 24193 24194 24195 24196 24197 24198 24199 24200 24201 24202 24203 24204 24205 24206 24207 24208 24209 24210 24211 24212 24213 24214 24215 24216 24217 24218 24219 24220 24221 24222 24223 24224 24225 24226 24227 24228 24229 24230 24231 24232 24233 24234 24235 24236 24237 24238 ...

result:

ok Accepted.

Test #40:

score: 10

Accepted

time: 98ms

memory: 118328kb

input:

10
48412 869174248 2
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:

24206 41210 45054 45055 45056 45057 45058 45059 45060 45061 45062 45063 45064 45065 45066 45067 45068 45069 45070 45071 45072 45073 45074 45075 45076 45077 45078 45079 45080 45081 45082 45083 45084 45085 45086 45087 45088 45089 45090 45091 45092 45093 45094 45095 45096 45097 45098 45099 45100 45101 ...

result:

ok Accepted.

Test #41:

score: 10

Accepted

time: 116ms

memory: 123496kb

input:

5
91193 4099928074 2
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:

45596 88928 90874 90875 90876 90877 90878 90879 90880 90881 90882 90883 90884 90885 90886 90887 90888 90889 90890 90891 90892 90893 90894 90895 90896 90897 90898 90899 90900 90901 90902 90903 90904 90905 90906 90907 90908 90909 90910 90911 90912 90913 90914 90915 90916 90917 90918 90919 90920 90921 ...

result:

ok Accepted.

Subtask #6:

score: 12

Accepted

Dependency #3:

100%

Accepted

Test #42:

score: 12

Accepted

time: 7ms

memory: 96604kb

input:

output:

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

result:

ok Accepted.

Test #43:

score: 12

Accepted

time: 11ms

memory: 97280kb

input:

output:

-1
-1
16 23 27 4 29 3 15 18 13 6 22 11 17 2 5 12 24 9 10 8 7 25 19 1 26 28 20 14 21 
-1
-1

result:

ok Accepted.

Test #44:

score: 12

Accepted

time: 7ms

memory: 95692kb

input:

output:

result:

ok Accepted.

Test #45:

score: 12

Accepted

time: 11ms

memory: 97848kb

input:

output:

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

result:

ok Accepted.

Test #46:

score: 12

Accepted

time: 11ms

memory: 97992kb

input:

output:

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

result:

ok Accepted.

Test #47:

score: 12

Accepted

time: 3ms

memory: 98020kb

input:

output:

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

result:

ok Accepted.

Test #48:

score: 12

Accepted

time: 8ms

memory: 98740kb

input:

output:

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

result:

ok Accepted.

Test #49:

score: 12

Accepted

time: 3ms

memory: 99116kb

input:

output:

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

result:

ok Accepted.

Test #50:

score: 12

Accepted

time: 3ms

memory: 98892kb

input:

output:

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

result:

ok Accepted.

Test #51:

score: 12

Accepted

time: 10ms

memory: 99384kb

input:

output:

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

result:

ok Accepted.

Test #52:

score: 12

Accepted

time: 8ms

memory: 98776kb

input:

output:

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

result:

ok Accepted.

Subtask #7:

score: 18

Accepted

Dependency #4:

100%

Accepted

Dependency #6:

100%

Accepted

Test #53:

score: 18

Accepted

time: 7ms

memory: 96352kb

input:

output:

result:

ok Accepted.

Test #54:

score: 18

Accepted

time: 12ms

memory: 105268kb

input:

output:

21 369 363 366 361 365 357 360 354 359 351 358 343 356 341 168 80 316 349 340 348 40 97 338 342 337 339 336 334 332 333 330 327 328 315 325 308 322 307 320 306 329 59 38 319 300 136 263 304 318 200 293 314 291 312 290 311 288 310 287 303 286 302 279 298 278 297 270 296 269 295 268 289 368 265 283 36...

result:

ok Accepted.

Test #55:

score: 18

Accepted

time: 3ms

memory: 96772kb

input:

1
1981 59778 1
581 1357
1357 1114
1319 822
822 1185
1143 365
619 708
708 1424
1424 1489
1489 1936
1936 1740
1789 1497
1497 387
387 1272
1272 485
1448 418
418 893
1011 1305
1305 176
1593 915
915 1594
1594 1432
1432 1794
1794 837
17 704
704 1542
1270 802
802 1879
1427 608
608 1723
1723 1288
1288 779
7...

output:

1215 1979 1980 1981 1977 1973 1970 1974 1971 1960 1972 1969 1959 1964 1967 1958 1962 1966 1957 1953 1965 1947 1951 1956 1945 1948 1954 1943 1946 1950 1940 1932 1942 1933 1930 1941 1931 1917 1939 1921 1910 1937 1918 1906 1934 1912 1904 1929 1909 1897 1928 1903 1895 1926 1902 1892 1922 1901 1888 1919 ...

result:

ok Accepted.

Test #56:

score: 18

Accepted

time: 8ms

memory: 99292kb

input:

1
1998 29319 1
93 1888
1888 701
701 643
643 1166
294 975
975 574
574 19
19 1224
1435 1480
72 1942
1707 613
613 1451
1272 769
1683 1050
1372 1242
1242 901
191 230
1702 562
562 883
1086 1964
1964 1852
1852 1955
1955 310
1165 1905
54 557
557 1182
1182 973
973 878
878 1950
1950 551
551 1473
1473 1921
11...

output:

430 151 1985 1995 1984 1992 1980 1982 1974 801 1872 1018 1163 411 1675 1644 677 1662 1961 1477 728 829 1741 370 187 1753 1842 1762 433 1451 613 1707 1152 1719 716 1345 499 1514 600 957 213 680 723 1844 1158 1797 857 1344 101 71 843 452 524 118 898 1119 465 1814 1279 755 516 1969 1959 1960 1956 1954 ...

result:

ok Accepted.

Test #57:

score: 18

Accepted

time: 8ms

memory: 98288kb

input:

1
1916 61288 2
395 1027
1610 1787
1787 357
189 139
139 675
675 1158
1158 1868
1868 1196
719 1579
1131 810
810 227
227 475
475 1060
1092 1602
1298 760
1390 211
211 1839
1839 99
99 618
618 1754
1754 1682
1682 529
529 1460
1555 1589
1589 152
152 1665
1665 1781
1649 1487
1487 870
870 144
144 934
750 162...

output:

1527 1914 1912 1911 1909 1910 1907 1905 1570 722 1675 1906 1898 1904 1895 1899 1894 1897 1892 1896 1890 1889 1888 1885 1882 1884 1869 1880 1865 1879 1858 1877 1857 1875 1856 1874 1852 1873 1849 1871 1847 1866 1843 1864 1842 1862 1835 1860 1830 1853 1828 55 486 672 1124 487 1851 1826 1848 1823 1845 5...

result:

ok Accepted.

Test #58:

score: 18

Accepted

time: 4ms

memory: 97800kb

input:

1
1835 91921 1
792 896
527 544
544 1461
1461 1426
1426 399
1350 1246
1246 496
496 227
227 799
799 546
945 779
779 418
1712 108
944 949
949 279
552 73
1311 1756
749 815
815 838
838 802
802 242
242 149
1482 1459
568 180
180 506
506 1270
758 1417
1417 203
898 178
178 386
386 920
920 467
715 76
76 1111
...

output:

784 796 1834 1830 1832 1824 1829 1810 1828 1802 1827 1794 1825 1793 1817 1790 1813 1789 1812 1788 1809 1785 1808 1784 1807 1780 1805 1779 1804 1775 1803 1769 1801 1767 1800 1765 1796 1763 1795 1756 1792 1755 1791 1753 1787 1752 1786 1751 1783 1749 1782 1744 1781 1743 1778 1739 1777 1738 1776 1736 17...

result:

ok Accepted.

Test #59:

score: 18

Accepted

time: 8ms

memory: 105256kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
13 39 37 38 36 32 33 28 34 19 15 25 30 4 31 18 14 24 17 23 16 21 12 20 35 11 7 29 9 5 27 8 3 22 6 2 10 1 26 
8 21 20 25 30 9 37 19 35 32 7 17 23 15 24 6 33 16 38 18 27 5 28 22 2 10 4 3 1 14 31 12 36 26 29 11 13 34 
-1
19 21 18 32 4 5 20 34 9 16 22 17 33 3 30 15 7 28 36 2 31 1...

result:

ok Accepted.

Test #60:

score: 18

Accepted

time: 4ms

memory: 102648kb

input:

output:

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

result:

ok Accepted.

Test #61:

score: 18

Accepted

time: 14ms

memory: 105356kb

input:

output:

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

result:

ok Accepted.

Test #62:

score: 18

Accepted

time: 8ms

memory: 105148kb

input:

output:

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

result:

ok Accepted.

Test #63:

score: 18

Accepted

time: 8ms

memory: 103700kb

input:

output:

94 99 88 93 91 81 92 78 73 87 77 71 84 52 74 61 70 65 60 69 67 4 95 82 6 64 56 59 63 18 72 25 54 21 86 98 34 96 68 48 62 57 55 47 53 49 76 20 75 83 97 38 14 79 46 51 40 44 50 39 37 31 45 85 30 3 10 36 35 26 29 33 27 24 80 28 66 58 89 41 32 23 11 22 19 8 13 16 42 7 12 15 5 9 1 90 2 43 17 
45 100 98 9...

result:

ok Accepted.

Test #64:

score: 18

Accepted

time: 7ms

memory: 104112kb

input:

output:

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

result:

ok Accepted.

Test #65:

score: 18

Accepted

time: 4ms

memory: 104360kb

input:

output:

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

result:

ok Accepted.

Test #66:

score: 18

Accepted

time: 7ms

memory: 104108kb

input:

output:

307 380 377 374 372 370 362 360 359 358 354 348 351 344 214 347 199 333 332 294 85 194 81 336 346 335 345 227 124 211 355 334 289 115 327 261 324 86 170 35 185 267 29 200 183 125 225 264 142 365 122 171 311 272 236 321 12 14 117 144 72 76 34 293 153 343 329 155 20 193 342 316 339 313 96 145 337 148 ...

result:

ok Accepted.

Test #67:

score: 18

Accepted

time: 7ms

memory: 105448kb

input:

output:

174 376 374 375 373 372 369 371 367 370 364 368 363 365 362 351 352 350 51 100 347 348 346 359 10 254 339 345 338 341 337 335 336 332 328 330 326 321 325 316 324 315 322 314 320 309 319 304 317 303 313 302 30 311 297 310 296 308 294 293 291 288 216 289 35 197 275 327 150 298 97 45 268 255 2 306 323 ...

result:

ok Accepted.

Subtask #8:

score: 10

Accepted

Dependency #7:

100%

Accepted

Test #68:

score: 10

Accepted

time: 20ms

memory: 95720kb

input:

output:

result:

ok Accepted.

Test #69:

score: 10

Accepted

time: 28ms

memory: 105988kb

input:

20
4739 5853376 2
241 1557
2727 144
828 4540
4356 4276
2664 1248
3140 3044
2673 2465
4472 4588
4088 1582
1402 837
249 2576
4222 2011
4326 3478
618 1837
2221 2758
4294 4571
4420 99
783 4166
2904 2230
2043 3395
4697 394
1658 1677
2315 931
4132 173
2863 4183
1156 2961
3832 4207
4175 2577
3526 2571
3844...

output:

3761 4739 4738 4736 4734 4735 4733 4731 4729 4730 4726 4728 4725 4727 4723 4724 4722 4720 4718 4719 4712 4717 4711 4716 4709 4715 4706 4714 4704 4713 4703 4710 4700 4708 4695 4707 4694 4705 4693 4702 4691 4701 4690 4699 4689 4698 4688 4697 4684 4696 4682 4692 4681 4687 4676 4686 4675 4685 4671 4683 ...

result:

ok Accepted.

Test #70:

score: 10

Accepted

time: 37ms

memory: 104460kb

input:

10
9775 28387496 2
4111 1845
5328 8463
5658 5847
3140 4296
2304 2863
3059 9597
3416 4942
4155 8323
5427 420
4277 6009
6681 2156
2015 6300
3901 7434
3626 7491
34 8881
2933 1589
2493 3247
3049 2124
7966 8151
7298 5798
4005 1543
6558 7955
7205 7231
6962 8747
9115 2347
6678 2313
6313 5913
5718 2087
4601...

output:

8467 9775 9773 9774 9770 9772 9768 9771 9765 9769 9764 9767 9763 9766 9762 9761 9758 9760 9754 9759 9752 9757 9745 9756 9739 9755 9738 9753 9735 9751 9734 9750 9732 9749 9725 9748 9724 9747 9722 9746 9721 9744 9720 9743 9718 9742 9717 9741 9715 9740 9713 9737 9709 9736 9707 9733 9705 9731 9704 9730 ...

result:

ok Accepted.

Test #71:

score: 10

Accepted

time: 37ms

memory: 100108kb

input:

5
18424 102019945 1
6009 5000
688 5707
7377 2483
17135 11887
11730 10212
8202 2298
10379 4241
11435 9713
12686 1606
7194 701
4130 17140
12866 7314
5553 17608
17154 14894
476 15049
8664 31
16244 10749
7130 14423
15077 15440
3494 14841
14846 5537
15852 16565
9158 1139
9750 14771
16068 5101
5313 2422
9...

output:

17055 4413 3728 18423 18424 18422 18421 18420 18419 18417 18418 18415 18416 18414 18413 18408 18412 18407 18411 18406 18410 18405 18409 18404 18401 18403 18400 18402 18399 18397 18398 18393 18396 18392 18395 18387 18394 18384 18391 18381 18390 18380 18389 18375 18388 18370 18386 18368 18385 18367 18...

result:

ok Accepted.

Test #72:

score: 10

Accepted

time: 40ms

memory: 101080kb

input:

3
31442 1897522 2
227 18045
19811 21817
17841 21143
23712 9546
31355 10107
2019 12690
10655 15526
21289 27919
21190 18604
762 28189
31092 22046
941 7045
25679 6271
341 5776
16779 28120
396 3989
18232 11559
24181 31300
6960 8713
12363 9404
18439 27196
16813 9762
10651 332
3494 20107
13995 26937
2428 ...

output:

12874 31368 31419 31359 31373 31286 31344 31280 31332 31278 31328 31251 31293 31239 31279 31232 31272 31231 31267 31218 31225 31169 31217 31157 31214 31139 31165 31105 31148 31094 31146 31055 31123 31053 31101 31009 31090 31008 31089 31003 31088 30984 31043 30966 30923 30962 30907 30886 30858 30884 ...

result:

ok Accepted.

Test #73:

score: 10

Accepted

time: 44ms

memory: 105516kb

input:

3
32308 277196163 1
28236 28059
13478 9068
28454 28849
16817 246
11618 9818
28123 4662
20902 9080
13907 9158
5441 10539
27228 25652
13268 4496
13075 15781
9747 15408
24294 13278
29091 28311
3433 30055
20111 22336
24462 24005
16412 2106
17953 18082
11530 16617
17947 4128
2459 26569
9247 18592
19713 1...

output:

16122 17937 32308 32306 32307 32303 32305 32299 32304 32296 32302 32295 32301 32294 32300 32292 32298 32291 32297 32290 32293 32289 32287 32288 32286 32285 32284 32281 32283 32280 32282 32278 32279 32275 32276 32274 32265 32273 32260 32271 32258 32270 32256 32269 32250 32268 32249 32267 32248 32266 ...

result:

ok Accepted.

Test #74:

score: 10

Accepted

time: 23ms

memory: 105948kb

input:

233
427 58203 1
279 292
169 156
224 109
215 332
268 84
335 383
381 6
166 228
261 252
47 241
118 197
136 140
31 80
329 149
241 351
387 61
400 208
60 219
187 199
116 365
420 186
288 98
427 55
391 305
192 40
88 339
278 308
87 322
221 185
415 360
285 295
422 140
10 218
359 92
15 286
286 33
102 396
246 1...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
201 42 390 391 385 389 383 388 382 387 380 386 376 384 375 381 374 379 372 378 371 377 368 373 365 370 362 369 361 367 360 366 358 364 350 363 347 359 343 357 342 356 341 355 309 339 354 338 353 337 352 335 351 333 349 330 348 329 346 328 345 326 344 324 340 32...

result:

ok Accepted.

Test #75:

score: 10

Accepted

time: 25ms

memory: 104136kb

input:

output:

5 3 1 4 8 7 2 9 6 
4 2 6 8 5 1 10 3 7 9 
7 3 6 2 8 4 1 9 10 5 
3 7 5 8 10 9 1 2 6 4 
4 3 7 5 8 9 2 6 1 
5 9 2 1 7 8 4 3 6 
7 8 2 9 6 1 5 10 3 4 
9 8 10 6 5 4 7 1 3 2 
5 4 7 1 9 2 6 3 8 
7 9 8 5 4 6 1 2 3 
2 8 6 3 5 9 7 4 1 
2 5 4 10 6 7 3 9 1 8 
4 1 9 5 3 7 8 10 2 6 
3 4 2 6 5 10 1 7 8 9 
5 8 9 4 7 ...

result:

ok Accepted.

Test #76:

score: 10

Accepted

time: 22ms

memory: 103960kb

input:

output:

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

result:

ok Accepted.

Test #77:

score: 10

Accepted

time: 23ms

memory: 104280kb

input:

output:

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

result:

ok Accepted.

Test #78:

score: 10

Accepted

time: 27ms

memory: 103128kb

input:

output:

65 100 98 99 97 96 94 95 92 93 90 91 89 87 88 81 86 80 85 76 84 73 83 71 82 70 79 68 78 66 75 64 41 74 61 72 59 69 57 67 56 60 55 58 54 47 53 46 52 45 51 42 50 40 44 38 43 37 39 31 36 30 35 28 34 27 17 49 77 24 13 33 20 29 19 25 15 23 12 48 22 10 21 8 16 7 18 14 5 63 62 6 11 4 9 1 32 3 2 26 
85 92 8...

result:

ok Accepted.

Test #79:

score: 10

Accepted

time: 28ms

memory: 104300kb

input:

500
181 10132 2
63 62
111 83
175 78
89 149
163 95
54 2
165 55
55 119
162 58
131 86
4 8
41 71
15 47
130 20
10 42
35 141
146 166
14 135
181 176
42 7
68 128
51 116
16 64
160 171
38 21
90 25
168 20
100 50
177 132
65 138
43 147
25 164
115 127
27 22
58 21
7 150
44 144
12 141
124 173
102 109
29 153
32 112
...

output:

135 181 180 178 179 176 177 175 174 173 172 169 171 168 170 166 167 165 163 164 160 162 157 161 156 159 155 158 153 152 149 151 147 150 145 148 144 146 143 136 142 131 141 130 139 124 138 122 137 119 134 118 133 116 132 114 129 111 128 110 127 109 126 108 125 105 123 104 121 103 120 102 117 100 115 ...

result:

ok Accepted.

Test #80:

score: 10

Accepted

time: 22ms

memory: 105380kb

input:

200
471 12114 2
415 145
297 397
304 440
14 104
181 443
273 49
105 78
84 2
212 53
432 390
394 451
468 286
127 263
113 238
171 196
59 117
392 349
215 94
356 442
344 338
192 86
66 257
241 450
306 26
272 142
161 384
58 196
218 463
93 23
312 372
54 308
308 68
452 345
51 247
418 76
122 8
198 139
424 108
5...

output:

387 465 470 460 466 459 462 458 457 440 455 434 453 430 450 428 436 427 435 425 432 424 415 422 413 416 397 410 396 408 390 403 386 401 383 393 377 385 369 379 368 363 358 354 223 39 45 370 442 356 259 444 240 280 235 174 319 438 88 405 202 142 272 107 167 56 151 25 324 247 51 37 380 74 64 72 129 30...

result:

ok Accepted.

Test #81:

score: 10

Accepted

time: 25ms

memory: 105872kb

input:

100
975 217172 2
649 311
744 359
221 637
308 496
259 838
859 382
738 637
17 87
454 452
546 664
703 942
867 284
754 964
12 467
114 932
36 393
390 469
42 328
115 480
462 329
39 8
233 588
86 130
325 316
872 258
341 967
967 162
941 288
687 871
258 356
321 468
581 476
31 813
133 538
635 824
331 377
71 50...

output:

932 975 974 973 971 972 968 970 964 966 961 963 960 962 959 958 957 954 956 952 955 947 953 945 951 944 950 943 949 941 948 938 946 936 942 929 940 928 939 925 933 924 931 921 930 917 927 916 922 914 920 912 919 910 918 906 915 904 913 902 911 897 909 893 907 891 903 890 901 888 900 886 896 884 895 ...

result:

ok Accepted.

Test #82:

score: 10

Accepted

time: 28ms

memory: 105448kb

input:

50
1867 423383 1
1402 1596
1768 1660
84 1611
368 1781
53 1341
996 1046
806 1866
1460 742
1359 1004
1863 605
489 250
388 1318
135 845
392 346
1257 855
654 77
490 640
1808 1148
384 614
1495 275
1196 1236
827 75
75 1712
254 726
1436 1432
1344 1476
728 739
1016 523
523 1837
381 1623
1703 1397
59 1827
52...

output:

833 1600 1867 1863 1866 1861 1865 1858 1862 1857 1860 1856 1855 1851 1854 1848 1853 1844 1852 1840 1849 1838 1843 1837 1841 1834 1836 1832 1835 1831 1833 1829 1825 1824 1823 1818 1819 1816 1813 1815 1812 1811 1810 1808 1809 1805 1794 1804 1791 1802 1790 1801 1785 1800 1781 1798 1779 1797 1777 1787 1...

result:

ok Accepted.

Subtask #9:

score: 22

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Dependency #8:

100%

Accepted

Test #83:

score: 22

Accepted

time: 72ms

memory: 94720kb

input:

output:

result:

ok Accepted.

Test #84:

score: 22

Accepted

time: 124ms

memory: 113432kb

input:

100
4914 5868584 2
4855 1980
1713 1299
1733 640
3936 2505
1258 1919
2989 2100
1549 1808
3837 534
2254 2130
459 1376
3914 200
2187 692
3465 2689
4501 1594
4516 3783
4095 3045
22 2133
1256 1369
1073 1136
646 3990
4506 3499
2663 3812
3649 3512
3573 2111
2241 2707
1879 2677
4216 2691
2878 1285
4604 4816...

output:

192 4914 4913 4911 4912 4910 4907 4909 4906 4908 4905 4903 4904 4902 4899 4900 4898 4896 4895 4893 4894 4892 4890 4888 4889 4887 4884 4886 4883 4885 4880 4882 4877 4881 4876 4878 4874 4875 4873 4872 4870 4871 4869 4868 4867 4863 4866 4858 4864 4856 4861 4855 4860 4853 4859 4851 4857 4847 4854 4845 4...

result:

ok Accepted.

Test #85:

score: 22

Accepted

time: 134ms

memory: 113632kb

input:

50
9264 14343522 2
4127 3748
8726 7859
1654 448
5251 8559
2277 3834
8033 4427
8913 6115
759 3415
671 312
1678 2639
6702 2797
3520 7485
464 1726
2509 6969
3491 6541
1904 4841
443 3242
6363 7280
2589 1882
2697 5015
9186 9026
125 70
2312 5699
5927 4834
4402 4396
7256 8408
2441 5044
1999 3156
564 3901
2...

output:

2153 9264 9260 9263 9259 9261 9258 9247 9256 9244 9255 9242 9254 9233 9252 9230 9249 9228 9248 9220 9245 9213 9243 9208 9239 9207 9238 9205 9237 9204 9236 9203 9235 9196 9234 9194 9232 9191 9231 9187 9229 9186 9227 9182 9226 9181 9223 9179 9221 9174 9219 9173 9218 9172 9217 9171 9216 9170 9215 9160 ...

result:

ok Accepted.

Test #86:

score: 22

Accepted

time: 122ms

memory: 111868kb

input:

50
9392 58225 1
6228 6729
316 3831
4383 827
4783 206
901 8057
8725 8920
6509 5267
2014 6918
7013 8718
699 1492
7298 8293
309 3846
5194 5883
3758 6754
7087 2643
2026 4947
7467 4209
5897 1024
7167 8508
4305 2042
6807 9031
2272 3612
7696 4195
3339 8474
8564 1256
8979 1773
3222 4076
4412 8107
27 3558
23...

output:

5717 5559 9375 9196 9366 521 1788 7784 778 7217 777 4753 6423 9167 4556 2929 4071 760 5441 4948 4662 4508 2217 2072 6214 19 2704 855 475 8096 7000 2178 3491 2720 7458 8853 2538 5481 325 5394 6836 9285 1256 8564 5976 836 4915 8944 3697 3840 8472 5983 2107 9380 7153 7429 5642 8294 1592 6869 4007 2656 ...

result:

ok Accepted.

Test #87:

score: 22

Accepted

time: 157ms

memory: 108136kb

input:

25
19790 20927306 2
4444 6276
14933 10108
6231 5388
15299 4203
17068 12794
10252 8287
6787 4058
2947 7053
16913 8475
5104 4109
10834 9443
11748 12927
8388 16660
4325 9605
16413 2446
16668 323
2038 4364
19597 2386
17857 2971
12045 2107
10345 15034
5324 4685
1910 9248
19068 3915
8777 3401
17337 2365
1...

output:

10911 19790 19784 19782 19777 19778 19776 19772 19769 19768 19766 19764 19759 19757 19758 19756 19750 19744 19749 19743 19741 19742 19735 19736 19732 19714 19725 19709 19724 19706 19723 19705 19722 19700 19721 19695 19718 19691 19715 19690 19711 19684 19708 19677 19702 19674 19699 19673 19698 19670 ...

result:

ok Accepted.

Test #88:

score: 22

Accepted

time: 158ms

memory: 113492kb

input:

25
19975 93145930 2
12432 1834
1881 14484
15930 10534
10845 7335
8074 9798
361 16500
1801 6929
4437 3207
14447 5118
6677 4193
1052 4088
869 640
15256 8605
8186 18363
15464 3806
5778 17272
9822 14677
5350 15754
1674 18160
1783 8216
15853 14470
14582 12437
2545 812
1606 18202
19624 9375
1895 6171
8629...

output:

6648 19974 19973 19968 19972 19964 19971 19963 19967 19961 19966 19958 19965 19957 19962 19956 19959 19953 19955 19951 19954 19950 19952 19949 19948 19945 19943 19944 19941 19942 19939 19940 19938 19937 19936 19935 19932 19934 19931 19933 19930 19929 19927 19928 19926 19924 19925 19922 19923 19920 1...

result:

ok Accepted.

Test #89:

score: 22

Accepted

time: 175ms

memory: 112180kb

input:

10
47976 591885312 2
5124 43680
2252 9516
19288 8740
28470 38971
44005 16449
35113 31009
7142 23054
26551 47176
10450 26089
21857 23087
41980 36670
42848 35489
10282 16403
5395 30470
15802 45845
17969 7447
34743 7617
34799 20623
34264 26807
33968 43764
29498 27833
40072 29805
28680 33112
22228 26794...

output:

29006 47974 47976 47972 47975 47971 47973 47970 47967 47969 47966 47968 47964 47965 47962 47961 47958 47960 47955 47959 47954 47957 47953 47956 47951 47952 47950 47945 47948 47944 47947 47942 47946 47940 47943 47937 47941 47933 47939 47929 47938 47924 47936 47922 47935 47921 47934 47919 47931 47918 ...

result:

ok Accepted.

Test #90:

score: 22

Accepted

time: 167ms

memory: 117160kb

input:

10
45442 215847028 1
18473 30982
44534 41274
2723 45201
13119 6426
38639 43918
31640 2906
32096 15308
1356 8922
22081 4880
45055 5993
13173 20550
16941 19759
16629 2018
19954 43873
13002 18173
11394 28098
41851 25383
5142 31705
27108 15842
35992 22440
32300 24908
6264 14876
8386 39768
27107 20226
11...

output:

4860 45440 45442 45438 45436 45426 45435 45423 45434 45417 45433 45416 45432 45415 45429 45410 45428 45409 45425 45406 45422 45399 45421 45398 45420 45395 45418 45394 45414 45393 45408 45392 45407 45391 45405 45387 45401 45386 45390 45379 45385 45375 45384 45374 45383 45364 45372 45363 45371 45359 4...

result:

ok Accepted.

Test #91:

score: 22

Accepted

time: 188ms

memory: 117428kb

input:

5
98026 412627902 2
48046 18927
13901 28466
35521 5201
80007 11667
80793 96581
55539 20025
5543 85851
55543 21411
29340 34851
29610 60263
18792 84130
32073 75581
78498 30643
1376 11678
50702 79538
3515 33613
58947 90914
32141 54510
97107 57425
16944 15325
26833 50683
53820 39405
4095 9382
40911 6943...

output:

89789 98022 98018 98020 98005 98019 98002 98014 97992 98011 97986 98010 97981 98008 97980 98000 97960 97990 97943 97984 97939 97979 97937 97975 97931 97974 97930 97972 97923 97967 97919 97962 97916 97961 97911 97958 97905 97947 97904 97945 97901 97940 97900 97933 97896 97924 97886 97918 97884 97917 ...

result:

ok Accepted.

Test #92:

score: 22

Accepted

time: 201ms

memory: 115660kb

input:

5
91305 1628174951 1
56198 20850
52916 85909
35476 56437
1834 9115
12192 10250
42982 57176
9593 27306
24150 48020
65107 42644
78643 42705
52340 56849
10078 23282
57269 5876
77632 26605
32767 24018
81204 21219
47096 12948
33055 2485
54922 15109
4406 72601
71077 36886
57706 24314
9215 42336
36145 6145...

output:

45523 22901 91301 91304 91300 91303 91299 91302 91298 91297 91293 91296 91289 91294 91287 91291 91285 91288 91283 91286 91279 91284 91278 91282 91272 91281 91269 91277 91265 91276 91261 91275 91260 91274 91258 91273 91257 91270 91256 91268 91255 91267 91254 91264 91253 91263 91252 91248 91247 91243 ...

result:

ok Accepted.

Test #93:

score: 22

Accepted

time: 289ms

memory: 155124kb

input:

1
472025 16043466085 1
417926 39623
195768 229314
370537 57531
267104 382113
170933 141578
53561 74294
250159 31886
9352 36181
322148 394068
117039 351210
300887 304015
24549 24940
114489 128610
411952 339863
71691 11387
73530 4523
10760 14371
149252 155462
22680 357719
350109 402379
152082 101050
2...

output:

323822 250496 472018 472024 472013 472023 472012 472021 472007 472020 472003 472019 472002 472016 471996 472011 471992 472001 471991 472000 471986 471998 471984 471994 471982 471993 471978 471989 471974 471988 471969 471985 471968 471971 471964 471970 471963 471965 471938 471960 471929 471954 471923...

result:

ok Accepted.

Test #94:

score: 22

Accepted

time: 107ms

memory: 102672kb

input:

output:

3 4 7 1 8 5 2 6 
7 6 5 4 1 3 2 8 
8 7 1 2 5 4 6 3 
2 5 7 4 1 6 8 3 
7 2 4 8 1 6 5 3 
1 6 4 2 8 7 5 3 
7 5 3 1 2 4 8 6 
2 6 1 8 4 5 7 3 
8 3 6 5 1 4 2 7 
5 2 8 1 7 3 4 6 
1 6 8 4 7 3 2 5 
6 4 5 7 2 3 8 1 
6 7 3 1 2 4 5 8 
4 2 6 3 5 1 8 7 
8 1 7 6 2 4 5 3 
4 6 8 5 1 3 2 7 
3 8 7 5 1 2 6 4 
3 1 6 2 7 8...

result:

ok Accepted.

Test #95:

score: 22

Accepted

time: 224ms

memory: 146028kb

input:

1
482724 69862381824 1
137472 24627
53394 136713
29923 24872
183115 104962
360179 53778
95044 16923
208793 216766
343809 82383
389111 122728
267129 163660
381943 86337
191746 130719
179638 171500
16541 49248
9266 60892
245541 12470
324537 105560
368925 467572
480713 67654
10418 410596
140876 300727
...

output:

181682 482724 482723 482718 482722 482717 482721 482715 482720 482713 482719 482711 482716 482709 482714 482708 482712 482707 482710 482704 482706 482703 482705 482702 482700 482701 482699 482698 482697 482696 482693 482695 482690 482694 482689 482692 482683 482691 482682 482688 482678 482687 482676...

result:

ok Accepted.

Test #96:

score: 22

Accepted

time: 243ms

memory: 145684kb

input:

1
466556 37068012357 1
296077 254374
55895 139417
250053 262476
281210 151748
361746 75307
38308 211
25635 226913
290473 170308
112117 207274
333222 333380
165721 128597
76733 301893
137129 112197
171945 20656
193257 43287
93646 249912
343755 80957
434796 359970
277965 34924
188290 4117
401431 43469...

output:

445753 86698 466556 466554 466555 466551 466553 466548 466552 466546 466550 466544 466549 466541 466547 466538 466545 466534 466542 466532 466539 466531 466529 466528 466527 466525 466526 466520 466524 466519 466523 466518 466521 466515 466516 466514 466512 466510 466511 466507 466508 466506 466505 ...

result:

ok Accepted.

Test #97:

score: 22

Accepted

time: 274ms

memory: 152544kb

input:

1
470507 15553613111 1
116590 375013
25458 460568
274726 423221
185476 26173
129323 115569
393959 379177
186613 320883
413505 47092
298840 72519
445171 170296
28563 18974
198881 343336
153370 1813
428633 372899
188361 262767
97460 411511
23648 449045
388428 367955
10793 398742
305885 3039
441903 422...

output:

353265 397678 470505 470507 470500 470498 470496 470495 470489 470486 470480 470483 470479 470478 470475 470474 470470 470464 470469 470463 470460 470461 470458 470451 470457 470447 470455 470439 470454 470438 470453 470428 470442 470427 470441 470426 470433 470422 470431 470399 470430 470395 470423...

result:

ok Accepted.

Test #98:

score: 22

Accepted

time: 269ms

memory: 151968kb

input:

1
484644 70415722676 2
387061 60091
283751 60069
107460 354884
445876 55307
338664 281406
388782 24215
35572 117625
177669 98530
7682 233035
116725 414416
355609 95819
475062 198221
241991 472832
44124 13983
140233 377622
213795 216775
272564 443204
119914 351907
326597 142211
466195 381175
457028 2...

output:

190723 484643 484644 484641 484642 484640 484639 484638 484637 484636 484635 484634 484632 484633 484631 484628 484630 484627 484629 484623 484626 484621 484625 484612 484624 484611 484622 484610 484620 484609 484619 484605 484618 484604 484617 484602 484616 484601 484615 484600 484614 484598 484613...

result:

ok Accepted.

Test #99:

score: 22

Accepted

time: 271ms

memory: 146716kb

input:

1
480049 66333578702 2
414780 52384
229954 204017
477598 350060
177290 395393
22600 399649
194443 4952
375752 445636
81605 302911
366288 84718
57315 335522
472784 367329
137447 408097
409021 236863
121965 347700
346918 58159
445793 183641
255068 367810
442172 237707
471652 352900
286081 25476
89138 ...

output:

76397 480044 480049 480043 480048 480041 480047 480040 480046 480039 480045 480038 480042 480037 480036 480034 480035 480031 480033 480030 480032 480025 480027 480021 480026 480018 480024 480013 480023 480009 480022 480003 480020 480002 480019 480001 480017 480000 480016 479999 480015 479994 480014 ...

result:

ok Accepted.

Test #100:

score: 22

Accepted

time: 78ms

memory: 104616kb

input:

1000
498 181292 1
55 405
423 313
133 192
359 39
367 203
366 42
100 76
358 263
183 445
87 27
114 402
331 371
272 424
394 194
417 268
285 284
328 59
125 495
495 364
201 407
310 18
337 283
213 154
346 229
16 65
341 480
315 252
393 19
7 153
365 86
95 144
287 349
262 470
332 295
424 255
336 491
491 311
6...

output:

-1
206 478 477 476 475 474 471 473 463 472 461 470 459 469 455 468 454 467 452 466 451 465 450 464 448 462 446 460 442 457 437 456 436 453 435 449 433 447 431 445 423 444 422 443 420 441 419 439 413 438 410 434 408 432 406 430 403 429 402 428 401 427 400 426 399 425 397 421 396 418 392 417 390 415 3...

result:

ok Accepted.

Test #101:

score: 22

Accepted

time: 103ms

memory: 105472kb

input:

output:

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

result:

ok Accepted.

Test #102:

score: 22

Accepted

time: 111ms

memory: 105612kb

input:

2000
230 11927 1
198 69
181 202
214 145
16 114
211 199
20 92
100 194
177 145
55 228
228 152
101 138
203 42
137 186
36 77
189 152
152 196
6 22
57 123
123 213
213 27
217 157
187 127
22 172
172 168
224 155
33 144
144 13
167 166
61 209
135 175
48 200
199 124
50 230
161 109
190 226
30 155
86 79
79 183
29...

output:

166 15 230 228 229 227 225 226 222 224 221 223 219 220 215 218 214 185 76 110 157 217 5 68 80 173 12 53 179 99 204 141 149 159 213 216 211 209 210 207 208 206 88 205 122 72 31 146 117 193 37 24 41 113 140 23 2 46 212 203 200 202 199 201 198 196 197 195 194 192 191 190 188 189 187 186 183 182 180 181...

result:

ok Accepted.

Test #103:

score: 22

Accepted

time: 102ms

memory: 104768kb

input:

output:

94 460 404 457 458 454 452 437 445 421 440 415 430 408 428 390 423 386 411 378 406 374 398 365 369 362 364 358 357 356 352 355 349 353 342 350 337 346 330 345 320 332 305 331 295 329 290 324 456 282 323 274 322 272 319 270 311 265 297 261 294 249 293 239 291 235 281 230 276 229 275 222 267 219 266 2...

result:

ok Accepted.

Test #104:

score: 22

Accepted

time: 114ms

memory: 110348kb

input:

output:

381 963 935 893 931 857 922 841 905 833 875 803 827 794 760 771 713 769 643 765 635 701 625 700 608 674 576 644 522 630 514 628 504 490 465 408 463 135 675 924 710 457 510 198 551 325 672 201 638 899 382 853 177 758 451 62 441 744 785 618 532 908 271 202 429 847 128 258 574 314 439 676 548 842 533 9...

result:

ok Accepted.

Test #105:

score: 22

Accepted

time: 103ms

memory: 110388kb

input:

500
962 55094 2
235 718
135 459
342 659
434 460
921 812
495 217
751 340
546 326
439 820
337 780
523 223
658 277
938 947
701 493
809 501
198 895
883 554
293 504
627 939
103 688
297 215
26 828
3 402
273 885
190 172
470 871
465 889
244 698
356 926
878 940
23 961
730 476
906 459
80 479
823 139
881 395
3...

output:

268 958 960 955 943 952 940 951 930 949 929 948 909 945 904 944 903 936 900 935 899 933 891 927 887 923 885 919 882 917 880 916 878 914 873 910 871 907 870 898 861 894 859 886 857 884 845 883 844 875 838 874 832 872 820 869 815 868 810 867 806 862 801 856 800 855 746 825 196 582 799 133 639 445 54 8...

result:

ok Accepted.

Test #106:

score: 22

Accepted

time: 121ms

memory: 114832kb

input:

100
4746 1051132 2
1237 3867
2107 4075
3048 3224
2208 1419
3875 1498
598 1118
4554 3504
1732 1316
1594 1279
3626 2781
2662 3766
3719 4529
4566 3799
178 2964
340 768
2823 3777
217 2269
2504 2945
345 4068
2882 3668
2116 471
2368 3872
606 1614
2884 961
1854 4389
4510 920
3424 2284
3637 2875
1692 2741
1...

output:

3134 4742 4746 4730 4737 4729 4734 4726 4728 4724 4727 4723 4721 4702 4719 4687 4718 4684 4716 4677 4699 4674 4694 4671 4690 4670 4689 4669 4678 4645 4676 4644 4668 4635 4667 4628 4666 4622 4659 4614 4657 4610 4652 4602 4649 4593 4648 4583 4646 4582 4643 4575 4642 4571 4641 4570 4636 4568 4634 4563 ...

result:

ok Accepted.

Test #107:

score: 22

Accepted

time: 129ms

memory: 112160kb

input:

100
4503 2286264 1
1641 2688
3396 2617
2562 833
1305 2310
638 850
2450 2086
1235 1661
4143 1757
3412 3937
1584 12
1159 736
3175 3109
1202 2747
3778 3893
1592 1029
203 982
3709 1326
2540 2325
2707 893
43 2008
2203 2422
1901 3772
559 3365
4355 2942
1770 3316
2864 2218
2544 359
763 4500
3537 2236
376 2...

output:

666 4500 4498 4493 4497 4488 4495 4487 4494 4482 4492 4479 4489 4475 4485 4474 4483 4471 4478 4470 4476 4462 4469 4461 4468 4455 4464 4454 4460 4452 4459 4449 4458 4447 4451 4446 4448 4445 4440 4444 4439 4442 4434 4441 4430 4437 4425 4436 4424 4435 4423 4429 4422 4427 4420 4421 4418 4414 4416 4413 4...

result:

ok Accepted.