QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#412005	#8359. travel	zhouhuanyi	100 ✓	714ms	214708kb	C++14	9.9kb	2024-05-15 22:52:01	2024-05-15 22:52:01

Judging History

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

[2024-05-15 22:52:01]
评测

测评结果：100
用时：714ms
内存：214708kb

查看

[2024-05-15 22:52:01]
提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
#include<cassert>
#include<cstdlib>
#include<random>
#define N 1000000
using namespace std;
mt19937 RAND(random_device{}());
const int inf=(int)(1e9);
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
	bool operator < (const reads &t)const
	{
		return num<t.num;
	}
};
reads tong[N+1],tongs[N+1];
int T,n,op,rt,rst,lengw,lengst,nws,length,lengths,belong[N+1],lg[N+1],depth[N+1],sdepth[N+1],sfa[N+1][21],ls[N+1],rs[N+1],ans[N+1],tans[N+1],pst,dque[N+1],top,fa[N+1],sz[N+1],cnt[N+1],dp[N+1],cl[N+1],maxp[N+1];
long long k,sk,res;
bool used[N+1];
vector<int>E[N+1];
vector<int>v[N+1];
set<int>s;
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
int lca(int x,int y)
{
	if (sdepth[x]<sdepth[y]) swap(x,y);
	for (int i=lg[n];i>=0;--i)
		if (sdepth[sfa[x][i]]>=sdepth[y])
			x=sfa[x][i];
	if (x==y) return x;
	for (int i=lg[n];i>=0;--i)
		if (sfa[x][i]!=sfa[y][i])
			x=sfa[x][i],y=sfa[y][i];
	return sfa[x][0];
}
int dis(int x,int y)
{
	return sdepth[x]+sdepth[y]-(sdepth[lca(x,y)]<<1);
}
void dfs(int x)
{
	used[x]=sz[x]=1,maxp[x]=0;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
			sdepth[E[x][i]]=sdepth[x]+1,sfa[E[x][i]][0]=x,dfs(E[x][i]),sz[x]+=sz[E[x][i]],maxp[x]=max(maxp[x],sz[E[x][i]]);
	maxp[x]=max(maxp[x],n-sz[x]);
	if (maxp[x]<maxp[rt]) rt=x;
	return;
}
void dfs2(int x)
{
	used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		{
			if (x==rt) cl[E[x][i]]=++lengw;
			else cl[E[x][i]]=cl[x];
			fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,dfs2(E[x][i]);
		}
	return;
}
int smerge(int x,int y)
{
	++nws,ls[nws]=x,rs[nws]=y;
	return nws;
}
void merge(int x,int y)
{
	if (v[x].size()>v[y].size()) swap(v[x],v[y]);
	for (int i=0;i<v[x].size();++i) v[y].push_back(v[x][i]);
	v[x].clear(),v[x].shrink_to_fit();
	return;
}
void dfs3(int x)
{
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]]==x)
			dfs3(E[x][i]),dp[x]+=dp[E[x][i]];
	cnt[x]+=dp[x];
	return;
}
void dfs4(int x)
{
	int scnt=1,d,ds=x,pv=-1;
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]]==x)
			dfs4(E[x][i]),scnt+=cnt[E[x][i]];
    scnt-=cnt[x],s.clear();
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]]==x)
			s.insert(E[x][i]);
	for (int i=1;i<=scnt;++i)
	{
		auto it=s.begin();
		if ((*it)!=pv) d=(*it);
		else
		{
			it++;
			if (it==s.end()) it--,d=(*it);
			else d=(*it);
		}
		if (d!=pv) ds=smerge(ds,v[d].back()),v[d].pop_back();
		else ds=smerge(v[d].back(),ds),v[d].pop_back();
		if (v[d].empty()) s.erase(d);
		pv=d;
	}
	v[x].push_back(ds);
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]]==x)
			merge(E[x][i],x);
	return;
}
bool get(int x)
{
	int d=x;
	while (d>n) d=ls[d];
	if (fa[d]==rt) return 1;
	d=x;
	while (d>n) d=rs[d];
	if (fa[d]==rt) return 1;
	return 0;
}
void dfs5(int x)
{
	if (x<=n) ans[++pst]=x;
	else dfs5(ls[x]),dfs5(rs[x]);
	return;
}
void dfs6(int x)
{
	if (x<=n) ans[++pst]=x;
	else dfs6(rs[x]),dfs6(ls[x]);
	return;
}
void adder(int x,int d)
{
	top=0;
	while (x!=rt) dque[++top]=x,x=fa[x];
	for (int i=1;i<=d;++i) cnt[dque[i]]++;
	return;
}
int get_maxn()
{
	int x=1,y=1,maxn=0;
	for (int i=1;i<=n;++i)
		if (dis(x,i)>maxn)
			y=i,maxn=dis(x,y);
	for (int i=1;i<=n;++i)
		if (dis(y,i)>maxn)
			x=i,maxn=dis(x,y);
	rst=x;
	return maxn;
}
bool dst[N+1];
bool cmp(int x,int y)
{
	return dst[x]<dst[y];
}
void dfs7(int x)
{
	used[x]=1,dst[x]=(x==rst);
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
			dfs7(E[x][i]),dst[x]|=dst[E[x][i]];
	return;
}
void dfs8(int x)
{
	ans[++pst]=x,used[x]=1,sort(E[x].begin(),E[x].end(),cmp);
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
			dfs8(E[x][i]);
	return;
}
bool check(int x)
{
	int d=x;
	while (d>n) d=ls[d];
	if (dis(d,rt)==1) return 1;
	d=x;
	while (d>n) d=rs[d];
	if (dis(d,rt)==1) return 1;
	return 0;
}
int main()
{
	int x,y,wst,sl;
	long long sk;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	T=read(),maxp[0]=inf;
	for (int qt=1;qt<=T;++qt)
	{
		n=read(),sk=k=read(),op=read();
		for (int i=1;i<=n;++i) E[i].clear(),used[i]=0;
		for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
		if (n==1&&k==0)
		{
			puts("1");
			continue;
		}
		if (op==1)
		{
			rt=rst=res=lengw=length=lengths=pst=0;
			for (int i=1;i<=n;++i) sfa[i][0]=0;
			sdepth[1]=1,dfs(1);
			for (int i=1;i<=lg[n];++i)
				for (int j=1;j<=n;++j)
					sfa[j][i]=sfa[sfa[j][i-1]][i-1];
			for (int i=1;i<=n;++i) used[i]=fa[i]=cnt[i]=dp[i]=ls[i]=rs[i]=0,v[i].clear();
			depth[rt]=0,dfs2(rt);
			for (int i=1;i<=n;++i) res+=(depth[i]<<1);
			if (k<((n-1)<<1)-get_maxn()||k>res-1)
			{
				puts("-1");
				continue;
			}
			if (k<((n-1)<<1))
			{
				k=((n-1)<<1)-k;
				for (int i=1;i<=n;++i)
					if (dis(rst,i)==k)
					{
						for (int j=1;j<=n;++j) used[j]=0;
						dfs7(i);
						for (int j=1;j<=n;++j) used[j]=0;
						dfs8(i);
						break;
					}
			}
			else
			{
				sl=0;
				while (1)
				{
					for (int i=1;i<=n;++i) shuffle(E[i].begin(),E[i].end(),RAND);
					wst=(sk&1)?1:2,k=sk+wst,lengw=length=lengths=pst=0,nws=n,k=(k>>1)-(n-1);
					for (int i=1;i<=n;++i) used[i]=cnt[i]=dp[i]=ls[i]=rs[i]=0,v[i].clear();
					for (int i=1;i<=n;++i)
						if (i!=rt)
							cnt[i]=1;
					for (int i=1;i<=n;++i)
						if (i!=rt)
						{
							for (int j=1;j<=E[i].size()-1;++j) tong[++length]=(reads){cl[i],i};
						}
					sort(tong+1,tong+length+1);
					if (RAND()&1) reverse(tong+1,tong+length+1);
					if (length&1) tongs[++lengths]=tong[(length+1)>>1];
					for (int i=1;i<=(length>>1);++i)
					{
						if (tong[i].num!=tongs[lengths].num) tongs[++lengths]=tong[i],tongs[++lengths]=tong[i+((length+1)>>1)];
						else tongs[++lengths]=tong[i+((length+1)>>1)],tongs[++lengths]=tong[i];
					}
					for (int i=1;i<=lengths;++i)
					{
						if (k>=depth[tongs[i].data]) dp[tongs[i].data]++,k-=depth[tongs[i].data];
						else if (k)
						{
							adder(tongs[i].data,k),k=0;
							break;
						}
					}
					dfs3(rt),length=lengths=0;
					for (int i=0;i<E[rt].size();++i)
					{
						dfs4(E[rt][i]);
						for (int j=0;j<v[E[rt][i]].size();++j) tong[++length]=(reads){i+1,v[E[rt][i]][j]};
					}
					sort(tong+1,tong+length+1);
					if (length&1) tongs[++lengths]=tong[(length+1)>>1];
					for (int i=1;i<=(length>>1);++i)
					{
						if (tong[i].num!=tongs[lengths].num) tongs[++lengths]=tong[i],tongs[++lengths]=tong[i+((length+1)>>1)];
						else tongs[++lengths]=tong[i+((length+1)>>1)],tongs[++lengths]=tong[i];
					}
					tongs[++lengths]=(reads){0,rt};
					if (wst==2)
					{
						for (int i=1;i<=lengths-1;++i) belong[i]=0; 
						for (int i=1;i<=lengths-1;++i)
							if (get(tongs[i].data))
								belong[tongs[i].num]=i;
						for (int i=1;i<=lengths-2;++i)
							if (belong[tongs[i].num]&&belong[tongs[i+1].num])
							{
								swap(tongs[belong[tongs[i].num]],tongs[i]),swap(tongs[belong[tongs[i+1].num]],tongs[i+1]);
								break;
							}
					}
					else
					{
						for (int i=1;i<=lengths-1;++i)
						{
							if (get(tongs[i].data)&&tongs[i].num==tongs[1].num)
							{
								swap(tongs[1],tongs[i]);
								break;
							}
							if (get(tongs[i].data)&&tongs[i].num==tongs[lengths-1].num)
							{
								swap(tongs[lengths-1],tongs[i]);
								break;
							}
						}
					}
					for (int i=1;i<=lengths;++i)
					{
						if (RAND()&1) dfs5(tongs[i].data);
						else dfs6(tongs[i].data);
					}
					bool opst=0;
					for (int i=1;i<=n;++i)
						if (dis(ans[i],ans[i%n+1])==wst)
						{
							opst=1,sl=i;
							break;
						}
					if (opst) break;
				}
				lengst=0;
				for (int i=sl;i>=1;--i) tans[++lengst]=ans[i];
				for (int i=n;i>=sl+1;--i) tans[++lengst]=ans[i];
				reverse(tans+1,tans+lengst+1);
				for (int i=1;i<=n;++i) ans[i]=tans[i];
			}
			for (int i=1;i<=n;++i) printf("%d ",ans[i]);
			puts("");
		}
		else
		{
			rt=res=length=lengths=lengw=pst=0,nws=n;
			for (int i=1;i<=n;++i) sfa[i][0]=0;
			sdepth[1]=1,dfs(1);
			for (int i=1;i<=lg[n];++i)
				for (int j=1;j<=n;++j)
					sfa[j][i]=sfa[sfa[j][i-1]][i-1];
			for (int i=1;i<=n;++i) used[i]=fa[i]=cnt[i]=dp[i]=ls[i]=rs[i]=0,v[i].clear();
			depth[rt]=0,dfs2(rt);
			for (int i=1;i<=n;++i) res+=(depth[i]<<1);
			if (k<((n-1)<<1)||k>res||(k&1))
			{
				puts("-1");
				continue;
			}
			k=(k>>1)-(n-1);
			for (int i=1;i<=n;++i)
				if (i!=rt)
					cnt[i]=1;
			for (int i=1;i<=n;++i)
				if (i!=rt)
				{
					for (int j=1;j<=E[i].size()-1;++j) tong[++length]=(reads){cl[i],i};
				}
			sort(tong+1,tong+length+1);
			if (length&1) tongs[++lengths]=tong[(length+1)>>1];
			for (int i=1;i<=(length>>1);++i)
			{
				if (tong[i].num!=tongs[lengths].num) tongs[++lengths]=tong[i],tongs[++lengths]=tong[i+((length+1)>>1)];
				else tongs[++lengths]=tong[i+((length+1)>>1)],tongs[++lengths]=tong[i];
			}
			for (int i=1;i<=lengths;++i)
			{
				if (k>=depth[tongs[i].data]) dp[tongs[i].data]++,k-=depth[tongs[i].data];
				else if (k)
				{
					adder(tongs[i].data,k),k=0;
					break;
				}
			}
			dfs3(rt),length=lengths=0;
			for (int i=0;i<E[rt].size();++i)
			{
				dfs4(E[rt][i]);
				for (int j=0;j<v[E[rt][i]].size();++j) tong[++length]=(reads){i+1,v[E[rt][i]][j]};
			}
			sort(tong+1,tong+length+1);
			if (length&1) tongs[++lengths]=tong[(length+1)>>1];
			for (int i=1;i<=(length>>1);++i)
			{
				if (tong[i].num!=tongs[lengths].num) tongs[++lengths]=tong[i],tongs[++lengths]=tong[i+((length+1)>>1)];
				else tongs[++lengths]=tong[i+((length+1)>>1)],tongs[++lengths]=tong[i];
			}
			tongs[++lengths]=(reads){0,rt};
			for (int i=1;i<=lengths;++i) dfs5(tongs[i].data);
			for (int i=1;i<=n;++i) printf("%d ",ans[i]);
			puts("");
		}
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2

Accepted

Test #1:

score: 2

Accepted

time: 4ms

memory: 60624kb

input:

output:

result:

ok Accepted.

Subtask #2:

score: 4

Accepted

Test #2:

score: 4

Accepted

time: 11ms

memory: 87140kb

input:

output:

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

result:

ok Accepted.

Test #3:

score: 4

Accepted

time: 9ms

memory: 87920kb

input:

output:

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

result:

ok Accepted.

Test #4:

score: 4

Accepted

time: 8ms

memory: 85272kb

input:

output:

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

result:

ok Accepted.

Test #5:

score: 4

Accepted

time: 4ms

memory: 86592kb

input:

output:

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

result:

ok Accepted.

Test #6:

score: 4

Accepted

time: 3ms

memory: 89568kb

input:

output:

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

result:

ok Accepted.

Test #7:

score: 4

Accepted

time: 11ms

memory: 89260kb

input:

output:

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

result:

ok Accepted.

Test #8:

score: 4

Accepted

time: 6ms

memory: 59632kb

input:

output:

result:

ok Accepted.

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #9:

score: 8

Accepted

time: 3ms

memory: 89596kb

input:

output:

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

result:

ok Accepted.

Test #10:

score: 8

Accepted

time: 0ms

memory: 88664kb

input:

output:

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

result:

ok Accepted.

Test #11:

score: 8

Accepted

time: 11ms

memory: 89288kb

input:

output:

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

result:

ok Accepted.

Test #12:

score: 8

Accepted

time: 11ms

memory: 88788kb

input:

output:

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

result:

ok Accepted.

Test #13:

score: 8

Accepted

time: 7ms

memory: 88576kb

input:

output:

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

result:

ok Accepted.

Test #14:

score: 8

Accepted

time: 14ms

memory: 86448kb

input:

output:

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

result:

ok Accepted.

Test #15:

score: 8

Accepted

time: 7ms

memory: 59676kb

input:

output:

result:

ok Accepted.

Subtask #4:

score: 14

Accepted

Test #16:

score: 14

Accepted

time: 3ms

memory: 87092kb

input:

output:

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

result:

ok Accepted.

Test #17:

score: 14

Accepted

time: 7ms

memory: 88380kb

input:

output:

9 8 7 6 5 4 3 2 1 
8 6 1 2 3 4 5 9 7 
9 8 7 6 5 4 3 2 1 
-1
6 4 2 1 8 3 9 5 7 
-1
-1
4 3 2 1 6 7 8 9 5 
-1
-1
-1
-1
-1
-1
5 4 8 1 9 3 7 2 6 
-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
7 3 9 1 2 8 4 5 6 
-1
-1
5 9 10 2 8 3 4 1 6 7 
-...

result:

ok Accepted.

Test #18:

score: 14

Accepted

time: 10ms

memory: 58988kb

input:

output:

result:

ok Accepted.

Test #19:

score: 14

Accepted

time: 7ms

memory: 89204kb

input:

output:

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

result:

ok Accepted.

Test #20:

score: 14

Accepted

time: 7ms

memory: 89544kb

input:

output:

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

result:

ok Accepted.

Test #21:

score: 14

Accepted

time: 7ms

memory: 89564kb

input:

output:

371 372 373 374 375 376 377 378 379 380 381 382 383 384 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: 9ms

memory: 88816kb

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:

121 302 139 303 169 304 168 305 167 306 166 307 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 308 142 309 141 310 140 311 170 312 138 313 137 314 136 315 135 316 134 317 133 318 132 293 131 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 ...

result:

ok Accepted.

Test #23:

score: 14

Accepted

time: 7ms

memory: 88936kb

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:

727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 725 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 ...

result:

ok Accepted.

Test #24:

score: 14

Accepted

time: 8ms

memory: 89900kb

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 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 926 925 924 923 922 921 920 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 899 898 897 896 895 894 893 892 891 890 889 888 887 886 885 ...

result:

ok Accepted.

Test #25:

score: 14

Accepted

time: 4ms

memory: 89048kb

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 1209 595 1222 594 1221 593 1220 592 1219 591 1218 589 590 1217 588 1216 587 1215 586 1214 585 1213 584 1212 583 1211 597 1210 598 1223 599 1208 600 1207 601 1206 602 1205 632 631 630 629 628 627 626 625 624 623 622 621 620 619 618 617 616 615 614 613 612 611 610 609 608 607 606 605 604 603 1204 ...

result:

ok Accepted.

Test #26:

score: 14

Accepted

time: 11ms

memory: 89344kb

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:

580 1501 690 1502 814 1503 813 1504 812 1505 811 810 809 808 807 806 805 804 803 802 801 800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 770 769 768 767 766 765 764 763 762 761 760 759 758 757 756 755 754 753 752 751 750 749 748...

result:

ok Accepted.

Subtask #5:

score: 10

Accepted

Dependency #4:

100%

Accepted

Test #27:

score: 10

Accepted

time: 22ms

memory: 59896kb

input:

output:

result:

ok Accepted.

Test #28:

score: 10

Accepted

time: 166ms

memory: 111576kb

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:

29585 76102 37289 76103 37298 76104 37297 76105 37296 76106 37295 76107 37294 76108 37293 76109 37292 76110 37291 76111 37290 76112 37299 76113 37288 76114 37287 76115 37286 76116 37285 76117 37284 76118 37283 76119 37282 76092 37281 76083 37308 76084 37317 76085 37316 76086 37315 76087 37314 76088 ...

result:

ok Accepted.

Test #29:

score: 10

Accepted

time: 159ms

memory: 210912kb

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:

240924 240923 240922 240921 240920 240919 240918 240917 240916 240915 240914 240913 240912 240911 240910 240909 240908 240907 240906 240905 240904 240903 240902 240901 240900 240899 240898 240897 240896 240895 240894 240893 240892 240891 240890 240889 240888 240887 240886 240885 240884 240883 240882...

result:

ok Accepted.

Test #30:

score: 10

Accepted

time: 166ms

memory: 214708kb

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:

149892 397265 176088 397266 176097 397267 176096 397268 176095 397269 176094 397270 176093 397271 176092 397272 176091 397273 176090 397274 176089 397275 176098 397276 176087 397277 176086 397278 176085 397279 176084 397280 176083 397281 176082 397282 176081 397283 176080 397255 176079 397246 176107...

result:

ok Accepted.

Test #31:

score: 10

Accepted

time: 251ms

memory: 214360kb

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:

183995 183996 183997 183998 183999 184000 184001 184002 184003 184004 184005 184006 184007 184008 184009 184010 184011 184012 184013 184014 184015 184016 184017 184018 184019 184020 184021 184022 184023 184024 184025 184026 184027 184028 184029 184030 184031 184032 184033 184034 184035 184036 184037...

result:

ok Accepted.

Test #32:

score: 10

Accepted

time: 243ms

memory: 204676kb

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:

114005 114006 114007 114008 114009 114010 114011 114012 114013 114014 114015 114016 114017 114018 114019 114020 114021 114022 114023 114024 114025 114026 114027 114028 114029 114030 114031 114032 114033 114034 114035 114036 114037 114038 114039 114040 114041 114042 114043 114044 114045 114046 114047...

result:

ok Accepted.

Test #33:

score: 10

Accepted

time: 50ms

memory: 87168kb

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 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 91 92 93 94 95 96 97 98 50 
-1
-1
-1
49 50...

result:

ok Accepted.

Test #34:

score: 10

Accepted

time: 98ms

memory: 87348kb

input:

output:

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

result:

ok Accepted.

Test #35:

score: 10

Accepted

time: 111ms

memory: 90920kb

input:

output:

118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 78 201 79 202 203 204 205 206 207 208 20...

result:

ok Accepted.

Test #36:

score: 10

Accepted

time: 124ms

memory: 88868kb

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:

793 2011 1007 2010 998 2009 999 2008 1000 2007 1001 2006 1002 2005 1003 2004 1004 2003 1005 2002 1006 2001 997 2000 1008 1999 1009 1998 1010 1997 1011 1996 1012 1995 1013 1994 1014 1993 1015 2022 1016 2031 987 2030 978 2029 979 2028 980 2027 981 2026 982 2025 983 2024 984 2023 985 2012 986 2021 1017...

result:

ok Accepted.

Test #37:

score: 10

Accepted

time: 131ms

memory: 90288kb

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:

2971 7562 3209 7561 3199 7560 3200 7559 3201 7558 3202 7557 3203 7556 3204 7555 3205 7554 3206 7553 3207 7552 3208 7551 3198 7550 3210 7549 3211 7548 3212 7547 3213 7546 3214 7545 3215 7544 3216 7543 3217 7542 3218 7574 3219 7584 3187 7583 3177 7582 3178 7581 3179 7580 3180 7579 3181 7578 3182 7577 ...

result:

ok Accepted.

Test #38:

score: 10

Accepted

time: 135ms

memory: 94516kb

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:

6029 6030 6031 6032 6033 6034 6035 6036 6037 6038 6039 6040 6041 6042 6043 6044 6045 6046 6047 6048 6049 6050 6051 6052 6053 6054 6055 6056 6057 6058 6059 6060 6061 6062 6063 6064 6065 6066 6067 6068 6069 6070 6071 6072 6073 6074 6075 6076 6077 6078 6079 6080 6081 6082 6083 6084 6085 6086 6087 6088 ...

result:

ok Accepted.

Test #39:

score: 10

Accepted

time: 154ms

memory: 102936kb

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 24167 24166 24165 24164 24163 24162 24161 24160 24159 24158 24157 24156 24155 24154 24153 24152 24151 24150 24149 24148 24147 24146 24145 24144 24143 24142 24141 24140 24139 24138 24137 24136 24135 24134 24133 24132 24131 24130 24129 24128 24127 24126 24125 24124 24123 24122 24121 24120 24119 ...

result:

ok Accepted.

Test #40:

score: 10

Accepted

time: 157ms

memory: 103732kb

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:

18219 36439 18227 36440 18226 36441 18225 36442 18224 36443 18223 36444 18222 36445 18221 36446 18220 36447 18228 36448 18218 36449 18217 36450 18216 36451 18215 36452 18214 36453 18213 36454 18212 36455 18211 36429 18237 36421 18245 36422 18244 36423 18243 36424 18242 36425 18241 36426 18240 36427 ...

result:

ok Accepted.

Test #41:

score: 10

Accepted

time: 156ms

memory: 117652kb

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:

30614 61026 30604 61027 30605 61028 30606 61029 30607 61030 30608 61031 30609 61032 30610 61033 30611 61034 30612 61035 30613 61025 30603 61024 30615 61023 30616 61022 30617 61021 30618 61020 30619 61019 30620 61018 30621 61017 30622 61016 30623 61015 30624 61047 30592 61071 30582 61060 61061 61062 ...

result:

ok Accepted.

Subtask #6:

score: 12

Accepted

Dependency #3:

100%

Accepted

Test #42:

score: 12

Accepted

time: 7ms

memory: 89448kb

input:

output:

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

result:

ok Accepted.

Test #43:

score: 12

Accepted

time: 3ms

memory: 87308kb

input:

output:

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

result:

ok Accepted.

Test #44:

score: 12

Accepted

time: 7ms

memory: 58464kb

input:

output:

result:

ok Accepted.

Test #45:

score: 12

Accepted

time: 4ms

memory: 88744kb

input:

output:

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

result:

ok Accepted.

Test #46:

score: 12

Accepted

time: 13ms

memory: 88832kb

input:

output:

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

result:

ok Accepted.

Test #47:

score: 12

Accepted

time: 11ms

memory: 88824kb

input:

output:

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

result:

ok Accepted.

Test #48:

score: 12

Accepted

time: 4ms

memory: 89260kb

input:

output:

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

result:

ok Accepted.

Test #49:

score: 12

Accepted

time: 8ms

memory: 88884kb

input:

output:

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

result:

ok Accepted.

Test #50:

score: 12

Accepted

time: 9ms

memory: 89340kb

input:

output:

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

result:

ok Accepted.

Test #51:

score: 12

Accepted

time: 4ms

memory: 88540kb

input:

output:

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

result:

ok Accepted.

Test #52:

score: 12

Accepted

time: 11ms

memory: 89088kb

input:

output:

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

result:

ok Accepted.

Subtask #7:

score: 18

Accepted

Dependency #4:

100%

Accepted

Dependency #6:

100%

Accepted

Test #53:

score: 18

Accepted

time: 7ms

memory: 60928kb

input:

output:

result:

ok Accepted.

Test #54:

score: 18

Accepted

time: 3ms

memory: 88368kb

input:

output:

95 234 82 180 301 191 210 55 145 72 32 160 307 115 92 261 37 317 183 49 249 99 211 215 6 80 349 14 168 316 33 369 12 293 58 200 71 43 18 213 28 86 177 272 286 127 214 195 189 152 252 227 259 22 262 291 124 221 17 54 238 120 239 31 157 188 78 356 285 269 220 315 141 158 362 89 11 288 323 66 23 266 14...

result:

ok Accepted.

Test #55:

score: 18

Accepted

time: 9ms

memory: 87784kb

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:

767 1344 435 1886 453 1928 1048 1094 287 1100 1137 852 368 1295 191 1224 1257 1383 283 49 1051 478 12 414 1597 1055 724 1391 422 232 143 1787 1198 89 88 164 522 1507 523 138 1525 1579 1154 492 691 923 91 1275 1218 1664 92 60 1938 1913 129 797 70 659 1745 188 1169 571 823 1026 740 1259 1012 1731 1222...

result:

ok Accepted.

Test #56:

score: 18

Accepted

time: 3ms

memory: 89488kb

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:

319 1812 32 351 229 1552 1530 446 387 1690 1201 1161 865 522 1061 1086 532 1964 1237 879 1936 208 998 1918 317 1791 1314 60 98 1037 1962 416 6 892 628 1007 1587 18 31 1238 152 1405 1412 75 238 700 1628 1674 534 1763 1626 417 1940 721 313 831 1039 1682 641 1424 325 209 1597 653 1523 1393 853 1176 127...

result:

ok Accepted.

Test #57:

score: 18

Accepted

time: 3ms

memory: 89452kb

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:

1195 761 1384 1586 1775 1453 1838 1906 182 1293 165 1570 722 94 1157 1329 1845 656 1790 528 258 416 1731 1904 998 912 1659 438 14 882 1633 1874 887 1084 1107 1407 766 1735 1618 485 1117 903 1857 1579 240 719 62 1601 263 503 536 588 1143 636 1465 1440 1705 205 1175 242 106 823 1294 740 586 937 12 559...

result:

ok Accepted.

Test #58:

score: 18

Accepted

time: 3ms

memory: 91528kb

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:

1433 1564 623 1431 1576 1380 1314 1027 1725 334 1381 168 1098 1025 69 794 6 564 65 837 1556 215 1774 1497 674 848 174 1073 1293 1113 1801 1518 386 262 431 1679 70 117 1828 902 572 362 1808 275 137 917 1589 1700 1659 1420 105 1305 296 1012 178 1074 898 1571 830 543 920 1694 467 341 254 650 1560 263 1...

result:

ok Accepted.

Test #59:

score: 18

Accepted

time: 7ms

memory: 89644kb

input:

output:

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

result:

ok Accepted.

Test #60:

score: 18

Accepted

time: 12ms

memory: 87328kb

input:

output:

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

result:

ok Accepted.

Test #61:

score: 18

Accepted

time: 9ms

memory: 89156kb

input:

output:

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

result:

ok Accepted.

Test #62:

score: 18

Accepted

time: 11ms

memory: 89248kb

input:

output:

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

result:

ok Accepted.

Test #63:

score: 18

Accepted

time: 4ms

memory: 91212kb

input:

output:

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

result:

ok Accepted.

Test #64:

score: 18

Accepted

time: 7ms

memory: 89392kb

input:

output:

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

result:

ok Accepted.

Test #65:

score: 18

Accepted

time: 12ms

memory: 89512kb

input:

output:

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

result:

ok Accepted.

Test #66:

score: 18

Accepted

time: 7ms

memory: 87396kb

input:

output:

346 126 90 370 239 186 257 358 91 74 349 372 5 214 150 55 194 81 199 294 85 333 332 347 76 153 34 72 293 117 121 29 267 185 35 170 86 324 261 144 171 327 266 89 106 306 152 365 264 125 200 351 203 122 142 225 183 115 61 66 343 190 177 288 292 45 204 315 303 281 33 339 289 334 355 211 124 227 220 23 ...

result:

ok Accepted.

Test #67:

score: 18

Accepted

time: 7ms

memory: 89260kb

input:

output:

99 174 326 236 74 263 67 136 301 126 43 175 46 80 92 140 118 128 18 253 182 161 63 183 112 346 368 328 29 56 280 185 55 229 213 189 69 315 37 344 239 251 105 127 3 220 152 252 214 20 86 274 125 48 162 33 212 203 240 196 248 159 226 228 181 130 234 81 164 345 291 95 144 246 310 270 311 64 231 317 319...

result:

ok Accepted.

Subtask #8:

score: 10

Accepted

Dependency #7:

100%

Accepted

Test #68:

score: 10

Accepted

time: 11ms

memory: 59360kb

input:

output:

result:

ok Accepted.

Test #69:

score: 10

Accepted

time: 35ms

memory: 89828kb

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:

2552 8 1873 2744 1682 1061 2992 3227 352 3541 1655 3951 3867 4397 4463 287 215 2763 2513 370 1627 1531 3147 2756 866 1925 1983 4019 1838 3757 4654 2281 110 819 2422 4377 637 1878 2292 663 4439 1323 1596 1678 2019 2105 3143 4718 1508 139 1183 3068 73 2655 3195 4340 2000 3203 1791 3316 1189 1330 349 3...

result:

ok Accepted.

Test #70:

score: 10

Accepted

time: 39ms

memory: 90064kb

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:

6311 4213 7832 7570 15 3116 1900 2466 465 9199 9522 3892 8580 6272 9531 5102 8387 2323 6632 909 3399 8232 5135 59 3962 6477 9132 7686 4309 461 7757 4850 5453 3975 197 82 6193 7861 7482 2629 7415 8149 3937 2436 7049 7388 3457 6030 6427 2873 7340 6250 5153 9765 3721 3173 5694 8120 780 9576 516 7225 89...

result:

ok Accepted.

Test #71:

score: 10

Accepted

time: 57ms

memory: 89940kb

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:

4611 2335 3462 16605 9379 2572 16121 7233 12643 6847 7635 16167 9652 18174 3822 17939 15899 14227 11979 2805 3805 14209 5453 12680 15136 6611 635 140 15574 553 4994 18013 13300 13066 10527 15816 434 13120 2336 14531 13687 7139 2169 12378 5021 17344 6486 7624 1930 10068 12774 10938 1663 13267 5487 18...

result:

ok Accepted.

Test #72:

score: 10

Accepted

time: 56ms

memory: 95736kb

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:

3483 4604 5343 5614 22779 25960 15152 31150 15601 7807 12097 20360 17748 3917 13680 18830 20165 18214 30595 2810 30264 3686 3752 14994 17820 17205 18394 2508 22661 4851 12625 20591 23914 30640 30857 2613 5685 11738 8037 5909 23177 1781 23698 7594 9837 30999 11152 912 28956 13721 27102 11534 23093 13...

result:

ok Accepted.

Test #73:

score: 10

Accepted

time: 69ms

memory: 97296kb

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:

6616 1570 663 15285 10877 23749 1194 14020 566 21023 15506 9866 18240 19652 13843 31550 21079 6219 29927 13068 5613 25839 17991 26351 19541 25744 16961 27116 4960 4977 6491 2172 9629 15954 28694 7693 2557 2312 21290 22103 2026 366 31381 1695 26739 20463 17699 20986 4046 15089 5974 19572 30810 19206 ...

result:

ok Accepted.

Test #74:

score: 10

Accepted

time: 21ms

memory: 88856kb

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
225 278 370 52 355 39 195 220 25 78 271 106 55 191 357 186 182 158 306 190 327 302 348 216 32 209 13 226 275 135 210 290 180 201 42 262 148 343 91 342 110 140 345 80 269 339 160 33 240 292 118 335 313 37 242 231 146 365 22 2 30 132 243 360 176 35 133 358 108 19...

result:

ok Accepted.

Test #75:

score: 10

Accepted

time: 24ms

memory: 88716kb

input:

output:

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

result:

ok Accepted.

Test #76:

score: 10

Accepted

time: 31ms

memory: 89332kb

input:

output:

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

result:

ok Accepted.

Test #77:

score: 10

Accepted

time: 32ms

memory: 89344kb

input:

output:

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

result:

ok Accepted.

Test #78:

score: 10

Accepted

time: 34ms

memory: 88780kb

input:

output:

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

result:

ok Accepted.

Test #79:

score: 10

Accepted

time: 36ms

memory: 89176kb

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:

175 97 90 139 111 94 83 37 41 129 71 12 150 35 7 141 10 76 42 89 102 149 109 74 164 33 103 177 25 132 63 121 62 174 18 43 136 147 148 16 105 64 131 142 86 34 49 14 146 135 154 28 119 113 165 123 55 163 152 95 99 137 169 3 114 85 110 106 5 98 38 32 166 112 6 52 11 126 122 117 15 69 47 1 44 61 144 158...

result:

ok Accepted.

Test #80:

score: 10

Accepted

time: 36ms

memory: 87196kb

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:

161 111 384 88 405 269 319 103 45 259 444 240 280 235 174 438 442 48 371 244 106 223 39 370 356 187 34 471 288 9 91 316 60 203 348 341 152 238 41 113 315 124 73 242 148 281 353 276 193 11 377 141 149 94 207 279 145 79 53 169 95 254 87 368 180 450 17 466 241 212 415 215 194 332 413 440 172 458 24 354...

result:

ok Accepted.

Test #81:

score: 10

Accepted

time: 39ms

memory: 89112kb

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:

521 895 461 951 928 797 135 865 953 944 648 737 938 109 728 766 746 219 282 731 587 460 553 101 866 118 476 887 575 251 194 95 487 262 861 523 142 693 342 973 305 780 756 79 227 884 317 858 232 49 585 208 590 459 922 314 313 573 652 664 429 546 623 468 557 790 929 594 515 36 627 306 602 685 457 531 ...

result:

ok Accepted.

Test #82:

score: 10

Accepted

time: 34ms

memory: 91104kb

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:

852 73 1501 429 1349 1049 822 168 1247 482 837 1595 553 117 1188 637 244 171 83 1539 279 301 1249 1241 1378 1507 434 404 670 1136 203 826 1645 142 139 971 600 1617 1639 1556 401 1402 1177 1783 782 1209 105 1765 452 417 293 109 1596 228 1097 1520 924 27 644 302 875 1774 1461 1029 422 1565 1302 1576 5...

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

memory: 60368kb

input:

output:

result:

ok Accepted.

Test #84:

score: 22

Accepted

time: 166ms

memory: 89376kb

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:

2701 2850 1360 3853 4452 3997 1151 3365 3474 1408 4281 4810 972 1592 1825 2176 769 608 1558 62 323 575 1102 946 1572 1456 3337 1838 844 1559 2006 1079 1186 3300 579 3548 3519 2349 1683 4581 3198 3545 3051 473 2989 4498 2100 2604 4440 2432 1250 2157 1028 2143 3447 3752 291 2277 4000 3364 2221 1799 86...

result:

ok Accepted.

Test #85:

score: 22

Accepted

time: 184ms

memory: 91392kb

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:

4623 1117 5127 3435 5338 6494 8660 5946 709 7851 7931 3376 3243 7848 4156 799 4154 4288 1560 3619 3452 4959 6342 5861 4613 3485 4727 4140 8639 3546 6183 3629 4412 7117 1934 3160 6318 2101 7173 8425 2611 6800 5017 3101 1933 5274 4813 5437 2398 4487 3299 8287 4256 4728 1394 7905 8714 1950 3283 2983 45...

result:

ok Accepted.

Test #86:

score: 22

Accepted

time: 189ms

memory: 90136kb

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:

268 5453 6208 1843 5929 6373 6487 3533 3378 1339 7100 1697 7641 183 7357 3105 637 7356 126 6201 7242 6370 9229 1934 4760 2893 4024 1688 2456 5345 7431 7536 5849 5865 4122 8196 8873 1667 5082 6176 68 3578 7163 1347 3698 6192 4438 2406 4164 1470 4110 5205 297 5146 959 2424 5947 4201 6210 2358 6622 297...

result:

ok Accepted.

Test #87:

score: 22

Accepted

time: 237ms

memory: 92488kb

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:

2625 7662 16665 12017 1090 5413 11725 2228 3545 7263 10115 15653 15845 18009 13802 9762 5620 7181 8646 11201 2439 6101 13121 8586 13348 15160 9348 5904 6250 5681 19538 15900 19766 666 2476 6941 16578 8701 18962 1949 2759 5451 7005 13616 18176 9569 18301 13283 14658 6965 9247 16092 10356 8356 11699 1...

result:

ok Accepted.

Test #88:

score: 22

Accepted

time: 228ms

memory: 94780kb

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:

3605 2481 5285 17514 2182 17609 19959 18439 16438 3641 8393 10929 6709 16169 18436 17427 8126 8414 11733 4125 4374 11381 12419 18794 13633 388 2640 13068 5399 9499 19709 17547 13386 11769 19023 2596 19079 10581 13882 4851 12367 1179 11948 6990 620 15756 13262 10426 7145 19301 11566 10913 18184 5099 ...

result:

ok Accepted.

Test #89:

score: 22

Accepted

time: 299ms

memory: 101152kb

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:

30180 28670 21788 46675 13059 17731 29854 19363 24225 2536 5703 8799 11688 24782 7511 26959 26937 967 19210 39749 2083 36679 39891 19948 37295 6911 39566 8739 30599 46578 38858 15256 26773 37781 43460 2792 12560 2133 19050 38363 1404 29915 37596 24572 14849 34109 14332 15738 14633 6711 11183 22796 3...

result:

ok Accepted.

Test #90:

score: 22

Accepted

time: 275ms

memory: 100900kb

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:

22882 21346 9911 16093 14009 3001 45400 30429 17104 43822 20549 26961 34970 10520 4896 30163 21106 44385 30164 26152 11332 29614 31398 8138 4921 2865 22698 11186 447 25422 10612 15917 40698 11417 3661 24008 33683 31928 14436 3180 9626 28287 9577 12199 33774 39948 44443 6229 41306 29365 24232 4806 31...

result:

ok Accepted.

Test #91:

score: 22

Accepted

time: 306ms

memory: 112168kb

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:

44516 12305 37076 29177 37207 93044 68285 2382 42127 64084 82517 67973 34122 22907 61473 17607 57493 23711 7556 28366 45104 1326 95611 43607 57939 54605 58337 89431 19577 86147 96040 46948 31956 40399 42661 31420 77329 63651 77593 53380 24134 37116 26538 28382 82441 75744 85533 39300 46841 11952 538...

result:

ok Accepted.

Test #92:

score: 22

Accepted

time: 363ms

memory: 114428kb

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:

73677 10151 16331 76693 91299 45444 71619 27304 53761 85280 76093 76815 85598 17872 17563 86047 65618 24621 67681 61554 6254 44653 18888 58404 41404 10255 10815 69555 38126 43415 18926 73545 21290 13049 65209 63714 88536 43376 38359 31365 65088 37381 54141 24754 81789 67123 25969 19195 40124 49036 4...

result:

ok Accepted.

Test #93:

score: 22

Accepted

time: 638ms

memory: 191732kb

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:

12112 153299 307517 251682 315395 276727 276339 244456 404545 469314 306887 332274 216895 328230 59607 249286 352073 390158 422782 397306 441004 258761 203991 119643 469998 269467 125824 334496 138501 87339 153558 141742 104084 159060 80421 232070 44627 230752 420560 61762 41116 146409 182231 382084...

result:

ok Accepted.

Test #94:

score: 22

Accepted

time: 111ms

memory: 89284kb

input:

output:

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

result:

ok Accepted.

Test #95:

score: 22

Accepted

time: 714ms

memory: 194488kb

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:

168155 164685 164207 78488 406306 352791 176191 319395 330127 369463 295503 138988 49569 202935 276518 185240 181675 310117 108818 153906 305763 2853 388278 361371 28663 154770 31854 345450 21113 450625 374744 51249 117244 400435 380822 327496 95790 86974 306300 14872 48600 478812 21262 182289 30876...

result:

ok Accepted.

Test #96:

score: 22

Accepted

time: 685ms

memory: 187240kb

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:

140264 123318 341573 6463 410131 206316 277553 444054 368250 313759 281590 461587 413798 254075 101063 443117 123944 397181 352353 100378 211141 361281 373179 64479 312325 155972 402277 168157 24201 404504 297591 254737 128341 228091 265047 302443 223709 417443 228699 158756 245271 353664 187112 136...

result:

ok Accepted.

Test #97:

score: 22

Accepted

time: 658ms

memory: 192420kb

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:

54498 331365 149316 400721 147191 76518 166955 84446 113256 38994 117494 58371 338561 355647 281967 56353 225709 450532 382406 427092 404036 65353 392454 159032 98291 108479 56366 98665 46801 197094 382867 214352 81404 32062 437563 89219 34344 179266 338932 371569 91243 291707 451499 199528 145491 4...

result:

ok Accepted.

Test #98:

score: 22

Accepted

time: 430ms

memory: 191300kb

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:

43836 167291 410656 144940 466315 152424 198707 399045 44743 233991 452550 396506 127875 222641 65199 13760 101729 318837 188181 31879 27976 149496 197613 302528 280000 74453 3788 146903 394600 360729 233216 448499 190607 181374 261500 340869 437414 46908 307385 180776 446844 361858 282453 350210 25...

result:

ok Accepted.

Test #99:

score: 22

Accepted

time: 399ms

memory: 192600kb

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:

402553 221494 173732 131261 26031 307691 64574 177397 257309 419990 75122 453650 149532 39733 396192 364127 267002 322772 134732 211392 432939 283214 207395 369461 22976 385480 390777 370067 26662 379576 421888 136313 445696 366591 408721 409519 402382 174084 102075 382120 386968 347771 309895 54052...

result:

ok Accepted.

Test #100:

score: 22

Accepted

time: 81ms

memory: 88696kb

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
424 175 321 353 84 203 157 408 162 60 19 369 92 74 208 191 95 336 268 62 246 241 50 271 393 104 197 370 432 128 427 423 332 44 464 94 460 350 296 391 134 258 200 210 334 35 113 290 130 79 103 466 85 82 300 212 399 55 299 409 248 302 168 106 64 39 229 237 4 425 207 165 46 469 51 331 436 389 87 325...

result:

ok Accepted.

Test #101:

score: 22

Accepted

time: 129ms

memory: 88448kb

input:

output:

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

result:

ok Accepted.

Test #102:

score: 22

Accepted

time: 140ms

memory: 87940kb

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:

38 78 28 51 17 220 59 227 79 170 81 86 44 183 10 52 180 39 197 32 125 105 64 202 20 181 85 133 75 201 143 169 50 112 102 230 61 91 209 63 121 229 73 1 97 21 36 109 161 77 62 58 207 100 186 167 204 141 159 35 15 48 26 90 200 203 40 42 47 84 188 154 89 7 49 33 144 218 13 137 221 149 130 43 9 194 106 1...

result:

ok Accepted.

Test #103:

score: 22

Accepted

time: 143ms

memory: 89704kb

input:

output:

94 345 106 374 386 1 48 30 266 276 6 358 260 353 294 421 49 362 322 4 302 64 36 116 388 187 208 226 119 439 148 32 79 464 107 307 172 465 335 438 120 10 450 426 420 209 278 33 330 460 458 101 349 337 235 383 385 41 31 42 263 87 181 216 428 69 305 222 50 95 183 217 47 300 203 63 231 419 196 433 121 9...

result:

ok Accepted.

Test #104:

score: 22

Accepted

time: 156ms

memory: 89120kb

input:

output:

121 285 700 130 304 375 490 776 300 319 704 175 357 850 779 655 32 313 742 693 364 297 627 393 722 145 334 917 836 966 360 679 646 485 179 508 956 38 793 699 94 157 657 605 146 409 509 631 724 302 170 346 166 523 829 139 7 479 339 73 602 142 872 823 526 247 448 229 869 864 751 686 649 324 111 831 93...

result:

ok Accepted.

Test #105:

score: 22

Accepted

time: 152ms

memory: 87416kb

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:

787 788 325 923 898 649 293 662 329 177 670 423 40 474 655 193 940 120 878 778 95 884 558 335 9 102 867 609 761 283 72 27 288 331 837 63 849 469 951 349 452 149 333 907 576 786 689 910 249 282 700 919 200 669 560 834 261 870 857 673 806 225 92 194 880 587 541 775 628 698 554 353 229 244 820 439 564 ...

result:

ok Accepted.

Test #106:

score: 22

Accepted

time: 170ms

memory: 91736kb

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:

2843 421 4685 3545 4689 1592 3694 1819 3631 3911 812 4318 2460 2528 3953 2909 3592 238 607 1486 1829 3587 2341 4140 3188 2387 2599 636 1815 3415 203 678 638 4074 3755 1426 3459 32 279 3031 415 1298 1885 3330 3470 1231 3765 1269 1303 726 1142 2991 4454 1262 1447 3045 1686 2285 1433 594 2584 2396 3281...

result:

ok Accepted.

Test #107:

score: 22

Accepted

time: 174ms

memory: 88628kb

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:

4100 1897 1788 1819 1159 736 1416 666 597 2397 83 2147 1662 1638 1851 1137 1527 2268 11 1570 2040 1549 4173 2362 3756 673 3249 4451 603 3615 2627 3556 728 3469 7 3165 2989 3926 4365 4209 4454 2673 3372 962 554 534 1627 3977 883 2727 4174 4098 4082 2906 695 1882 1528 449 2577 1892 4306 3344 1677 4353...

result:

ok Accepted.