QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#449165	#8359. travel	do_while_true	100 ✓	306ms	158680kb	C++20	7.9kb	2024-06-20 19:35:36	2024-06-20 19:35:37

Judging History

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

[2024-06-20 19:35:37]
评测

测评结果：100
用时：306ms
内存：158680kb

查看

[2024-06-20 19:35:36]
提交

answer

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<array>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int mod=998244353;
inline void cadd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void cdel(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int del(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
int qpow(int x,int y){
	int s=1;
	while(y){
		if(y&1)s=1ll*s*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return s;
}
const int N=500010;
int n,op;
ll m;
namespace sub2{
	vi eg[N];
	int mx[N],siz[N],rt;
	ll mxans;
	int fa[N],dep[N];
	int ok[N];
	priority_queue<pii>Q[N];
	vi vec[N],has[N];
	int bl[N];
	void getrt(int x,int fa){
		siz[x]=mx[x]=1;
		for(auto v:eg[x])if(v!=fa){
			getrt(v,x);siz[x]+=siz[v];
			cmax(mx[x],siz[v]);
		}cmax(mx[x],n-siz[x]);
		if(mx[x]<mx[rt])rt=x;
		mxans+=2*min(siz[x],n-siz[x]);
	}
	void dfs1(int x,int pa,int t){
		dep[x]=dep[pa]+1;
		if(dep[x]>1)Q[t].push(mp(dep[x],x));
		for(auto v:eg[x])if(v!=pa){
			dfs1(v,x,t);
		}
	}
	void dfs2(int x,int pa,int t){
		bl[x]=x;
		if(ok[x])bl[x]=bl[pa];
		vec[bl[x]].pb(x);
		for(auto v:eg[x])if(v!=pa)dfs2(v,x,t);
		if(bl[x]==x){
			has[t].pb(x);
		}
	}
	void main(){
		mxans=0;
		for(int i=1;i<=n;i++){
			vi().swap(eg[i]);
			dep[i]=mx[i]=siz[i]=0;
			fa[i]=dep[i]=ok[i]=0;
			while(!Q[i].empty())Q[i].pop();
		}
		for(int i=1,u,v;i<n;i++){
			read(u,v);
			#ifdef debug
				cout<<u<<' '<<v<<'\n';
			#endif
			eg[u].pb(v);eg[v].pb(u);
		}
		mx[rt=0]=N;
		getrt(1,0);
		if(m%2==1 || m>mxans || m<2*n-2){puts("-1");return ;}
		for(auto v:eg[rt])dfs1(v,rt,v);
		priority_queue<pii>q;
		for(auto v:eg[rt])if(Q[v].size())q.push(mp(Q[v].size(),v));
		ll now=mxans;
		while(now>m){
			int t=q.top().se;q.pop();
			while(1){
				int x=Q[t].top().se;Q[t].pop();
				if(now-(dep[x]-1)*2<m){
					continue;
				}
				ok[x]=1;
				now-=(dep[x]-1)*2;
				break;
			}
			if(Q[t].size())q.push(mp(Q[t].size(),t));
		}
		for(int i=1;i<=n;i++)vi().swap(vec[i]),vi().swap(has[i]);
		for(auto v:eg[rt])dfs2(v,rt,v);
		while(!q.empty())q.pop();
		for(auto v:eg[rt])q.push(mp(has[v].size(),v));
		vi va;
		vi ans;
		while(q.size()>=2){
			int x=q.top().se;q.pop();
			int y=q.top().se;q.pop();
			int u=has[x].back(),v=has[y].back();
			has[x].pop_back();has[y].pop_back();
			va.pb(u);
			va.pb(v);
			if(!has[x].empty())q.push(mp(has[x].size(),x));
			if(!has[y].empty())q.push(mp(has[y].size(),y));
		}
		if(!q.empty()){
			int x=q.top().se;q.pop();
			while(!has[x].empty()){
				int u=has[x].back();
				has[x].pop_back();
				va.pb(u);
			}
		}
		for(auto i:va)for(auto j:vec[i])ans.pb(j);
		ans.pb(rt);
		for(auto i:ans)cout<<i<<' ';
		cout<<'\n';
	}
}
namespace sub1{
	vi eg[N];
	namespace Tree{
		int dep[N],fa[N];
		int ban[N],banp;
		void dfs1(int x,int pa){
			dep[x]=dep[pa]+1;fa[x]=pa;
			for(auto v:eg[x])if(v!=pa)dfs1(v,x);
		}
		vi ans;
		void dfs2(int x,int pa){
			if(x!=banp)ans.pb(x);
			for(auto v:eg[x])if(v!=pa){
				if(ban[v])continue;
				dfs2(v,x);
			}
			for(auto v:eg[x])if(v!=pa){
				if(ban[v])dfs2(v,x);
			}
		}
		void solve(){
			for(int i=1;i<=n;i++)dep[i]=fa[i]=ban[i]=0;banp=0;
			dfs1(1,0);
			int U=max_element(dep+1,dep+n+1)-dep;
			dfs1(U,0);
			int V=max_element(dep+1,dep+n+1)-dep;
			if(m<2*n-dep[V]-1){
				puts("-1");
				return ;
			}
			int d=2*n-2-m;
			int p=V;
			while(dep[p]-1>d)p=fa[p];
			for(int i=p;i;i=fa[i])ban[i]=1;
			banp=p;
			vi().swap(ans);
			dfs2(U,0);
			ans.pb(p);
			for(int i:ans)cout<<i<<' ';
			cout<<'\n';
		}
	}
	int mx[N],siz[N],rt;
	ll mxans;
	int fa[N],dep[N];
	int ok[N];
	priority_queue<pii>Q[N];
	vi vec[N],has[N];
	int bl[N];
	void getrt(int x,int fa){
		siz[x]=mx[x]=1;
		for(auto v:eg[x])if(v!=fa){
			getrt(v,x);siz[x]+=siz[v];
			cmax(mx[x],siz[v]);
		}cmax(mx[x],n-siz[x]);
		if(mx[x]<mx[rt])rt=x;
		mxans+=2*min(siz[x],n-siz[x]);
	}
	void dfs1(int x,int pa,int t){
		dep[x]=dep[pa]+1;
		if(dep[x]>1)Q[t].push(mp(dep[x],x));
		for(auto v:eg[x])if(v!=pa){
			dfs1(v,x,t);
		}
	}
	void dfs2(int x,int pa,int t){
		bl[x]=x;
		if(ok[x])bl[x]=bl[pa];
		vec[bl[x]].pb(x);
		for(auto v:eg[x])if(v!=pa)dfs2(v,x,t);
		if(bl[x]==x){
			has[t].pb(x);
		}
	}
	void main(){
		if(n==1){
			if(m==0)puts("1");
			else puts("-1");
			return ;
		}
		for(int i=1;i<=n;i++)vi().swap(eg[i]);
		for(int i=1,u,v;i<n;i++){
			read(u,v);eg[u].pb(v);eg[v].pb(u);
			#ifdef debug
				cout<<u<<' '<<v<<'\n';
			#endif
		}
		if(m<2*n-2)return Tree::solve();
		int r=m%2==0?2:1;
		if(m%2==0)m+=2;
		else m+=1;
		//op=2
		mxans=0;
		for(int i=1;i<=n;i++){
			dep[i]=mx[i]=siz[i]=0;
			fa[i]=dep[i]=ok[i]=0;
			while(!Q[i].empty())Q[i].pop();
		}
		mx[rt=0]=N;
		getrt(1,0);
		if(m%2==1 || m>mxans || m<2*n-2){puts("-1");return ;}
//		assert(0);
		for(auto v:eg[rt])dfs1(v,rt,v);
		priority_queue<pii>q;
		for(auto v:eg[rt])if(Q[v].size())q.push(mp(Q[v].size(),v));
		ll now=mxans;
		while(now>m){
			int t=q.top().se;q.pop();
			while(1){
				int x=Q[t].top().se;Q[t].pop();
				if(now-(dep[x]-1)*2<m){
					continue;
				}
				ok[x]=1;
				now-=(dep[x]-1)*2;
				break;
			}
			if(Q[t].size())q.push(mp(Q[t].size(),t));
		}
		for(int i=1;i<=n;i++)vi().swap(vec[i]),vi().swap(has[i]);
		for(auto v:eg[rt])dfs2(v,rt,v);
		while(!q.empty())q.pop();
		for(auto v:eg[rt]){
			reverse(has[v].begin(),has[v].end());
			q.push(mp(has[v].size(),v));
		}
		vi va;
		vi ans;
		while(q.size()>=2){
			int x=q.top().se;q.pop();
			int y=q.top().se;q.pop();
			int u=has[x].back(),v=has[y].back();
			has[x].pop_back();has[y].pop_back();
			va.pb(u);
			va.pb(v);
			if(!has[x].empty())q.push(mp(has[x].size(),x));
			if(!has[y].empty())q.push(mp(has[y].size(),y));
		}
		if(!q.empty()){
			int x=q.top().se;q.pop();
			while(!has[x].empty()){
				int u=has[x].back();
				has[x].pop_back();
				va.pb(u);
			}
		}
		if(r==1){
			ans.pb(rt);
			for(auto i:va){
				if(i==va.back())reverse(vec[i].begin(),vec[i].end());
				for(auto j:vec[i])ans.pb(j);
			}
		}
		else{
			int len=va.size();
			int u=va[len-1],v=va[len-2];
			for(auto i:vec[u])ans.pb(i);
			ans.pb(rt);
			for(int i=0;i<=len-3;i++){
				for(auto j:vec[va[i]])ans.pb(j);
			}
			reverse(vec[v].begin(),vec[v].end());
			for(auto i:vec[v])ans.pb(i);
		}
		for(auto i:ans)cout<<i<<' ';
		cout<<'\n';
		return ;
	}
}
void solve(){
	read(n,m,op);
	#ifdef debug
		cout<<n<<' '<<m<<' '<<op<<'\n';
	#endif
	if(n==2){
		int u,v;read(u);read(v);
		if(m==op)puts("1 2");
		else puts("-1");
		return ;
	}
	if(op==1)return sub1::main();
	else return sub2::main();
}
signed main(){
	int T;read(T);
	#ifdef debug
		cout<<T<<'\n';
	#endif
	while(T--)solve();
    #ifdef do_while_true
//		cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
	#endif
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2

Accepted

Test #1:

score: 2

Accepted

time: 7ms

memory: 40376kb

input:

output:

result:

ok Accepted.

Subtask #2:

score: 4

Accepted

Test #2:

score: 4

Accepted

time: 4ms

memory: 63072kb

input:

output:

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

result:

ok Accepted.

Test #3:

score: 4

Accepted

time: 4ms

memory: 56876kb

input:

output:

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

result:

ok Accepted.

Test #4:

score: 4

Accepted

time: 4ms

memory: 60980kb

input:

output:

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

result:

ok Accepted.

Test #5:

score: 4

Accepted

time: 3ms

memory: 62968kb

input:

output:

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

result:

ok Accepted.

Test #6:

score: 4

Accepted

time: 3ms

memory: 56824kb

input:

output:

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

result:

ok Accepted.

Test #7:

score: 4

Accepted

time: 7ms

memory: 61220kb

input:

output:

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

result:

ok Accepted.

Test #8:

score: 4

Accepted

time: 8ms

memory: 44588kb

input:

output:

result:

ok Accepted.

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #9:

score: 8

Accepted

time: 13ms

memory: 63216kb

input:

output:

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

result:

ok Accepted.

Test #10:

score: 8

Accepted

time: 7ms

memory: 60920kb

input:

output:

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

result:

ok Accepted.

Test #11:

score: 8

Accepted

time: 3ms

memory: 46640kb

input:

output:

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

result:

ok Accepted.

Test #12:

score: 8

Accepted

time: 7ms

memory: 56892kb

input:

output:

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

result:

ok Accepted.

Test #13:

score: 8

Accepted

time: 3ms

memory: 56860kb

input:

output:

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

result:

ok Accepted.

Test #14:

score: 8

Accepted

time: 8ms

memory: 60976kb

input:

output:

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

result:

ok Accepted.

Test #15:

score: 8

Accepted

time: 4ms

memory: 46568kb

input:

output:

result:

ok Accepted.

Subtask #4:

score: 14

Accepted

Test #16:

score: 14

Accepted

time: 4ms

memory: 61020kb

input:

output:

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

result:

ok Accepted.

Test #17:

score: 14

Accepted

time: 4ms

memory: 63068kb

input:

output:

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

result:

ok Accepted.

Test #18:

score: 14

Accepted

time: 4ms

memory: 48612kb

input:

output:

result:

ok Accepted.

Test #19:

score: 14

Accepted

time: 4ms

memory: 63036kb

input:

output:

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

result:

ok Accepted.

Test #20:

score: 14

Accepted

time: 7ms

memory: 59156kb

input:

output:

45 44 46 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 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 49 42 48 43 47 
48 50 51 47 52 46 53 45 54 44 55 43 56...

result:

ok Accepted.

Test #21:

score: 14

Accepted

time: 12ms

memory: 63332kb

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: 63340kb

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:

191 189 188 192 187 193 186 194 185 195 184 196 183 197 182 198 181 199 180 200 179 201 178 202 177 203 176 204 175 205 174 206 173 207 172 208 171 209 170 210 169 211 168 212 167 213 166 214 165 215 164 216 163 217 162 218 161 219 160 220 159 221 158 222 157 223 156 224 155 225 154 226 153 227 152 ...

result:

ok Accepted.

Test #23:

score: 14

Accepted

time: 7ms

memory: 46972kb

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:

968 1347 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 1405 1...

result:

ok Accepted.

Test #24:

score: 14

Accepted

time: 4ms

memory: 49244kb

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 961 958 962 963 957 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 10...

result:

ok Accepted.

Test #25:

score: 14

Accepted

time: 3ms

memory: 47276kb

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 918 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 17 1819 18 1818 19 1817 20 1816 21 1815 22 1814 23 1813 24 1812 25 1811 26 1810 27 1809 28 1808 29 1807 30 1806 31 1805 32 1804 33 1803 34 1802 35 1801 36 1800 37 1799 38 17...

result:

ok Accepted.

Test #26:

score: 14

Accepted

time: 13ms

memory: 49096kb

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

result:

ok Accepted.

Subtask #5:

score: 10

Accepted

Dependency #4:

100%

Accepted

Test #27:

score: 10

Accepted

time: 43ms

memory: 46632kb

input:

output:

result:

ok Accepted.

Test #28:

score: 10

Accepted

time: 129ms

memory: 88552kb

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:

46524 46522 46525 46521 46526 46520 46527 46519 46528 46518 46529 46517 46530 46516 46531 46515 46532 46514 46533 46513 46534 46512 46535 46511 46536 46510 46537 46509 46538 46508 46539 46507 46540 46506 46541 46505 46542 46504 46543 46503 46544 46502 46545 46501 46546 46500 46547 46499 46548 46498 ...

result:

ok Accepted.

Test #29:

score: 10

Accepted

time: 148ms

memory: 143800kb

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 240926 240923 240927 240922 240928 240921 240929 240920 240930 240919 240931 240918 240932 240917 240933 240916 240934 240935 240915 240936 240914 240937 240913 240938 240912 240939 240911 240940 240910 240941 240909 240942 240908 240943 240907 240944 240906 240945 240905 240946 240904 240947...

result:

ok Accepted.

Test #30:

score: 10

Accepted

time: 135ms

memory: 158680kb

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:

247382 247380 247383 247379 247384 247378 247385 247377 247386 247376 247387 247375 247388 247374 247389 247373 247390 247372 247391 247371 247392 247370 247393 247369 247394 247368 247395 247367 247396 247366 247397 247365 247398 247364 247399 247363 247400 247362 247401 247361 247402 247360 247403...

result:

ok Accepted.

Test #31:

score: 10

Accepted

time: 130ms

memory: 158084kb

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:

245323 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 394449...

result:

ok Accepted.

Test #32:

score: 10

Accepted

time: 112ms

memory: 153764kb

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:

228007 38771 38770 38769 38768 38767 38766 38765 38764 38763 38762 38761 38760 38759 38758 38757 38756 38755 38754 38753 38752 38751 38750 38749 38748 38747 38746 38745 38744 38743 38742 38741 38740 38739 38738 38737 38736 38735 38734 38733 38732 38731 38730 38729 38728 38727 38726 38725 38724 38723...

result:

ok Accepted.

Test #33:

score: 10

Accepted

time: 52ms

memory: 62948kb

input:

output:

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 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 
-1
-1
-1
47 48...

result:

ok Accepted.

Test #34:

score: 10

Accepted

time: 94ms

memory: 63028kb

input:

output:

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

result:

ok Accepted.

Test #35:

score: 10

Accepted

time: 88ms

memory: 61076kb

input:

output:

116 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 67 66 65 64 63 62 61 60 ...

result:

ok Accepted.

Test #36:

score: 10

Accepted

time: 109ms

memory: 64496kb

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:

1213 1211 1214 1210 1215 1209 1216 1208 1217 1207 1218 1206 1219 1205 1220 1204 1221 1203 1222 1202 1223 1201 1224 1200 1225 1199 1226 1198 1227 1197 1228 1196 1229 1195 1230 1194 1231 1193 1232 1192 1233 1191 1234 1190 1235 1189 1236 1188 1237 1187 1238 1186 1239 1185 1240 1184 1241 1183 1242 1182 ...

result:

ok Accepted.

Test #37:

score: 10

Accepted

time: 114ms

memory: 68240kb

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:

4585 4583 4586 4582 4587 4581 4588 4580 4589 4579 4590 4578 4591 4577 4592 4576 4593 4575 4594 4574 4595 4573 4596 4572 4597 4571 4598 4570 4599 4569 4600 4568 4601 4567 4602 4566 4603 4565 4604 4564 4605 4563 4606 4562 4607 4561 4608 4560 4609 4559 4610 4558 4611 4557 4612 4556 4613 4555 4614 4554 ...

result:

ok Accepted.

Test #38:

score: 10

Accepted

time: 120ms

memory: 72392kb

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:

12053 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942 1941 1940 1939 1938 1937 1936 1935 1934 1933 1932 1931 1930 1929 1928 1927 1926 1925 1924 1923 1922 1921 1920 1919 1918 1917 1916 1915 1914 1913 1912 1911 1910 1909 1908 1907 1906 1905 1904 1903 1902...

result:

ok Accepted.

Test #39:

score: 10

Accepted

time: 136ms

memory: 77404kb

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:

24170 24168 24171 24167 24172 24166 24173 24165 24174 24164 24175 24163 24176 24162 24177 24161 24178 24160 24179 24159 24180 24158 24181 24157 24182 24156 24155 24183 24154 24184 24153 24185 24152 24186 24151 24187 24150 24188 24149 24189 24148 24190 24191 24192 24193 24194 24195 24196 24197 24198 ...

result:

ok Accepted.

Test #40:

score: 10

Accepted

time: 116ms

memory: 82852kb

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:

24208 24206 24209 24205 24210 24204 24211 24203 24212 24202 24213 24201 24214 24200 24215 24199 24216 24198 24217 24197 24218 24196 24219 24195 24220 24194 24221 24193 24222 24192 24223 24191 24224 24190 24225 24189 24226 24188 24227 24187 24228 24186 24229 24185 24230 24184 24231 24183 24232 24182 ...

result:

ok Accepted.

Test #41:

score: 10

Accepted

time: 121ms

memory: 101340kb

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:

45598 45596 45599 45595 45600 45594 45601 45593 45602 45592 45603 45591 45604 45590 45605 45589 45606 45588 45607 45587 45608 45586 45609 45585 45610 45584 45611 45583 45612 45582 45613 45581 45614 45580 45615 45579 45616 45578 45617 45577 45618 45576 45619 45575 45620 45574 45621 45573 45622 45572 ...

result:

ok Accepted.

Subtask #6:

score: 12

Accepted

Dependency #3:

100%

Accepted

Test #42:

score: 12

Accepted

time: 0ms

memory: 46672kb

input:

output:

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

result:

ok Accepted.

Test #43:

score: 12

Accepted

time: 7ms

memory: 56816kb

input:

output:

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

result:

ok Accepted.

Test #44:

score: 12

Accepted

time: 3ms

memory: 48848kb

input:

output:

result:

ok Accepted.

Test #45:

score: 12

Accepted

time: 7ms

memory: 56928kb

input:

output:

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

result:

ok Accepted.

Test #46:

score: 12

Accepted

time: 3ms

memory: 55080kb

input:

output:

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

result:

ok Accepted.

Test #47:

score: 12

Accepted

time: 7ms

memory: 56896kb

input:

output:

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

result:

ok Accepted.

Test #48:

score: 12

Accepted

time: 4ms

memory: 56936kb

input:

output:

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

result:

ok Accepted.

Test #49:

score: 12

Accepted

time: 3ms

memory: 56888kb

input:

output:

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

result:

ok Accepted.

Test #50:

score: 12

Accepted

time: 3ms

memory: 57132kb

input:

output:

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

result:

ok Accepted.

Test #51:

score: 12

Accepted

time: 7ms

memory: 56820kb

input:

output:

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

result:

ok Accepted.

Test #52:

score: 12

Accepted

time: 7ms

memory: 56924kb

input:

output:

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

result:

ok Accepted.

Subtask #7:

score: 18

Accepted

Dependency #4:

100%

Accepted

Dependency #6:

100%

Accepted

Test #53:

score: 18

Accepted

time: 3ms

memory: 48676kb

input:

output:

result:

ok Accepted.

Test #54:

score: 18

Accepted

time: 6ms

memory: 63040kb

input:

output:

264 21 47 171 42 74 75 26 39 312 27 112 278 296 290 184 174 332 144 88 244 5 291 273 78 198 356 185 288 363 149 357 265 271 254 20 256 325 165 354 125 164 103 208 221 253 191 46 329 59 38 319 300 136 263 55 321 57 145 40 183 97 338 43 36 369 229 168 80 316 349 310 200 293 289 367 286 53 133 177 213 ...

result:

ok Accepted.

Test #55:

score: 18

Accepted

time: 6ms

memory: 46972kb

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:

389 52 1196 191 1228 555 1224 1097 28 1257 1875 695 1744 433 1718 767 1931 906 1344 723 1633 1137 245 1700 852 1426 1688 368 878 687 435 886 167 1886 1534 1906 453 472 1979 1928 550 289 1048 869 220 224 507 1436 1094 1616 875 920 790 1128 1170 810 320 1571 195 620 1568 1242 39 1290 1783 1651 1491 94...

result:

ok Accepted.

Test #56:

score: 18

Accepted

time: 3ms

memory: 46800kb

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:

1870 1493 1825 828 212 1880 1293 225 369 270 1492 399 569 1511 1757 27 522 886 865 1070 1101 1570 550 215 1956 181 155 1576 605 99 1501 20 1363 689 1338 1863 636 500 967 1080 1804 665 1445 1183 1661 966 947 1386 466 191 1335 1583 1341 1478 3 1771 1023 1934 1500 1913 1909 818 49 1969 1515 1059 1377 1...

result:

ok Accepted.

Test #57:

score: 18

Accepted

time: 7ms

memory: 49004kb

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:

1272 1527 1519 1365 251 1086 1615 1761 631 1361 1083 89 944 388 123 826 1332 1614 837 923 1657 443 1170 1078 962 1585 158 1746 169 77 246 271 497 1219 842 1720 1244 1343 559 1146 1300 1853 62 1183 205 417 1440 1136 263 1246 1143 1889 636 501 536 453 1117 1508 240 1879 903 781 1857 357 1528 474 958 9...

result:

ok Accepted.

Test #58:

score: 18

Accepted

time: 7ms

memory: 46864kb

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:

1819 1161 690 870 85 249 1219 1250 1405 1693 1062 1060 638 765 176 843 503 1685 945 1644 779 884 220 787 418 1323 785 1593 484 609 1137 975 1195 233 603 390 74 191 972 963 517 420 565 1307 946 1552 460 1614 986 59 1086 107 1016 303 1802 206 228 1125 919 472 1363 1468 1465 1317 1429 1440 1488 154 299...

result:

ok Accepted.

Test #59:

score: 18

Accepted

time: 5ms

memory: 63208kb

input:

output:

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

result:

ok Accepted.

Test #60:

score: 18

Accepted

time: 4ms

memory: 62960kb

input:

output:

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

result:

ok Accepted.

Test #61:

score: 18

Accepted

time: 8ms

memory: 61152kb

input:

output:

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

result:

ok Accepted.

Test #62:

score: 18

Accepted

time: 4ms

memory: 61180kb

input:

output:

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

result:

ok Accepted.

Test #63:

score: 18

Accepted

time: 8ms

memory: 61020kb

input:

output:

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

result:

ok Accepted.

Test #64:

score: 18

Accepted

time: 12ms

memory: 63072kb

input:

output:

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

result:

ok Accepted.

Test #65:

score: 18

Accepted

time: 4ms

memory: 63076kb

input:

output:

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

result:

ok Accepted.

Test #66:

score: 18

Accepted

time: 12ms

memory: 63088kb

input:

output:

260 373 28 74 90 186 66 257 354 370 6 18 120 358 305 164 177 336 190 75 343 282 129 335 279 222 178 114 119 93 312 325 221 246 103 187 10 192 320 213 310 290 97 36 62 63 345 265 330 329 235 234 159 1 165 54 359 280 146 30 377 70 238 331 80 362 52 291 220 227 124 211 355 334 289 115 327 261 324 86 17...

result:

ok Accepted.

Test #67:

score: 18

Accepted

time: 3ms

memory: 61072kb

input:

output:

174 32 156 65 371 8 14 71 293 99 169 24 38 133 206 115 237 131 104 286 278 266 9 60 324 114 350 297 3 191 15 225 119 93 89 64 31 36 59 147 27 342 1 176 84 370 113 243 302 195 141 187 221 154 40 139 26 260 184 194 179 58 70 322 167 177 28 5 316 338 123 52 341 6 47 365 94 325 76 326 213 74 189 16 244 ...

result:

ok Accepted.

Subtask #8:

score: 10

Accepted

Dependency #7:

100%

Accepted

Test #68:

score: 10

Accepted

time: 12ms

memory: 46856kb

input:

output:

result:

ok Accepted.

Test #69:

score: 10

Accepted

time: 29ms

memory: 65156kb

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:

2520 3761 1800 3180 4642 4465 2557 599 1749 4242 2870 2111 4179 1149 2106 901 736 3076 4710 3461 182 1319 302 426 1851 3528 1501 4500 4 4690 748 3250 104 2101 2263 3673 2859 3962 3255 1027 194 406 1344 3226 3321 2543 1804 983 1155 1473 2486 4374 3964 1829 2424 2866 3721 146 3631 266 3013 3826 2217 1...

result:

ok Accepted.

Test #70:

score: 10

Accepted

time: 27ms

memory: 66492kb

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 9562 1384 4274 5964 456 899 6883 3080 41 6799 1790 1515 4853 6796 2095 7940 1630 8108 5142 9085 2185 3819 1604 2745 7780 8676 2865 5271 676 2682 6740 7821 7502 6026 3216 8525 9024 3524 2518 7835 9244 72 7515 6528 9420 4239 7464 8965 722 5307 7161 2443 1377 9483 9359 5557 9264 9123 9156 1206 339...

result:

ok Accepted.

Test #71:

score: 10

Accepted

time: 35ms

memory: 61172kb

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:

11725 4413 10850 3257 14793 462 6096 927 15815 434 6145 4994 14095 635 13232 15136 8332 15574 17939 3462 14227 11979 6847 7635 16167 3822 7233 9652 4054 17909 9362 6187 8920 9811 16581 1276 7308 11052 10406 16472 12111 1471 3256 13081 10139 15213 15869 14222 14209 13663 11819 1944 17210 2973 3918 40...

result:

ok Accepted.

Test #72:

score: 10

Accepted

time: 41ms

memory: 57420kb

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:

14547 12874 25551 26556 20114 8404 15317 8348 18909 25420 18799 7318 2572 30556 8203 25153 23941 31225 6202 7518 1977 14642 2762 31123 899 27207 21808 15049 18993 10405 8966 1742 15054 20432 22845 31344 5282 13256 23863 24835 2971 11813 21445 9465 14075 15537 15724 30707 9373 9059 4474 22634 26336 1...

result:

ok Accepted.

Test #73:

score: 10

Accepted

time: 40ms

memory: 53272kb

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:

18397 14112 14806 21544 28078 4859 19125 13518 5544 6684 2338 14912 4881 22761 28155 10967 11352 14025 12677 27530 7517 29770 30830 15859 21155 20652 14702 12356 587 10817 24443 20840 10908 407 4492 7942 1007 16147 11898 3372 10222 5135 23198 17679 6141 23524 11879 21434 3813 14978 5658 16450 21630 ...

result:

ok Accepted.

Test #74:

score: 10

Accepted

time: 15ms

memory: 61212kb

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
298 148 135 32 290 271 226 355 209 370 158 309 278 378 60 357 280 41 14 363 5 108 35 133 335 366 292 134 37 22 140 146 342 160 264 85 80 48 83 62 375 38 204 321 213 103 47 367 287 130 104 387 141 219 57 185 142 45 300 373 311 323 97 215 40 384 307 218 251 314 3...

result:

ok Accepted.

Test #75:

score: 10

Accepted

time: 28ms

memory: 63004kb

input:

output:

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

result:

ok Accepted.

Test #76:

score: 10

Accepted

time: 28ms

memory: 61160kb

input:

output:

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

result:

ok Accepted.

Test #77:

score: 10

Accepted

time: 33ms

memory: 63064kb

input:

output:

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

result:

ok Accepted.

Test #78:

score: 10

Accepted

time: 25ms

memory: 63328kb

input:

output:

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

result:

ok Accepted.

Test #79:

score: 10

Accepted

time: 23ms

memory: 61636kb

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 154 28 152 113 99 123 169 95 114 137 166 3 6 85 11 34 47 98 103 126 83 117 71 69 109 1 164 62 144 18 156 136 106 148 97 105 139 86 94 49 37 82 76 56 149 50 74 92 33 173 132 66 121 159 174 80 147 104 64 161 142 46 30 67 107 20 143 23 171 24 153 91 127 87 172 79 96 151 155 88 101 9 72 178 167 45 1...

result:

ok Accepted.

Test #80:

score: 10

Accepted

time: 26ms

memory: 65788kb

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:

471 387 316 26 348 255 27 42 108 104 284 455 160 29 206 168 32 4 363 229 119 369 427 89 139 271 251 1 13 101 328 126 318 71 465 390 234 52 296 457 262 69 62 114 340 397 100 267 134 323 393 435 260 170 162 57 430 82 314 99 78 453 163 232 293 63 36 253 434 67 320 396 325 462 385 28 410 249 350 386 190...

result:

ok Accepted.

Test #81:

score: 10

Accepted

time: 36ms

memory: 63892kb

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:

937 932 257 839 821 551 952 659 158 175 613 188 586 810 92 955 697 558 449 896 121 458 422 582 70 302 874 104 29 172 945 644 614 235 910 254 74 734 272 798 345 87 883 268 793 564 136 58 456 89 182 495 307 674 505 119 619 399 295 146 277 319 329 30 543 433 412 170 381 795 281 968 491 379 430 624 943 ...

result:

ok Accepted.

Test #82:

score: 10

Accepted

time: 28ms

memory: 64384kb

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:

491 580 102 257 1114 1170 1754 985 10 878 465 529 133 1609 31 220 356 218 1191 1835 592 773 1654 199 721 22 68 754 106 1012 1561 45 273 219 718 419 1857 1564 1798 374 982 312 868 396 776 490 570 687 1030 886 1213 569 1460 456 1282 193 167 1495 305 1853 181 1187 1454 930 1232 1400 1103 1860 1314 1494...

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

memory: 46632kb

input:

output:

result:

ok Accepted.

Test #84:

score: 22

Accepted

time: 125ms

memory: 66912kb

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:

2393 192 1286 2788 2231 2388 1852 2965 4072 3312 3542 2781 2428 393 2104 3884 559 4268 376 3512 2654 1034 1042 2380 1586 999 2417 1460 693 510 2680 4309 4535 550 3501 2451 3178 333 2940 3864 396 3359 900 1616 2741 470 2061 4461 3050 3360 176 2847 553 485 3375 343 20 488 2174 4550 511 2248 659 2119 2...

result:

ok Accepted.

Test #85:

score: 22

Accepted

time: 147ms

memory: 70324kb

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:

7377 2153 3922 8379 7289 7493 4986 7601 8717 5226 540 7739 2034 3536 6627 7727 4166 356 8140 9055 6217 3070 1362 4543 5852 2774 8492 9260 843 5436 6103 7767 1012 8002 2834 7325 3228 3332 4977 237 6710 8608 5706 4563 4697 6585 4790 760 4002 2326 1815 5377 3787 7803 6506 9075 4192 8702 6914 8961 5657 ...

result:

ok Accepted.

Test #86:

score: 22

Accepted

time: 132ms

memory: 68116kb

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:

8895 2515 8930 851 2378 7334 6597 2581 3899 4002 2941 9366 5877 7612 1509 5659 4571 6351 3805 7059 6563 4813 1272 4990 1738 4783 1669 77 2666 5974 1178 6753 5244 2725 3657 1961 2400 258 7645 861 391 1820 1504 3096 8755 8615 154 8984 3303 6810 5459 5241 8439 7166 6151 3056 2034 4401 8523 6946 2310 33...

result:

ok Accepted.

Test #87:

score: 22

Accepted

time: 168ms

memory: 69048kb

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:

12777 10911 11473 9084 6665 3713 15568 5825 17256 3578 971 10794 18661 17135 16364 12387 6228 11135 12469 13239 16620 10878 11644 7346 18943 1006 10851 19540 1633 18435 6654 11365 5299 7267 12626 14819 3206 2134 18095 16099 7886 16407 17712 6952 969 3379 9732 2644 19065 12743 17393 1292 1298 6295 10...

result:

ok Accepted.

Test #88:

score: 22

Accepted

time: 173ms

memory: 71216kb

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 13968 890 13202 6538 11687 3718 19750 17839 8689 12856 1004 10767 13858 8178 1600 7576 17933 14385 2977 13065 18344 16162 17408 8952 19244 13295 1720 1209 11498 14508 9276 4348 4141 5490 9395 4144 3280 7782 13196 3096 14805 12248 5474 3423 5916 13901 10138 8043 6033 2041 5647 14492 18120 16778 ...

result:

ok Accepted.

Test #89:

score: 22

Accepted

time: 198ms

memory: 74332kb

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:

38337 29006 20515 30821 3296 24014 22777 42620 1570 21270 18111 16456 4990 1188 29546 2552 18310 28063 38402 5440 12622 10577 47407 35412 33481 1083 12724 19403 46432 4578 22916 26836 11598 45457 5417 36859 23588 5587 26871 39935 19955 27433 27892 38642 32532 43428 32914 35128 19073 7 9009 30731 209...

result:

ok Accepted.

Test #90:

score: 22

Accepted

time: 203ms

memory: 82216kb

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 38435 10030 35083 5484 11420 2257 21349 30279 16537 38283 17679 36692 32903 43534 6026 30944 35554 45114 36718 43663 2346 30395 13968 21989 11317 41059 4046 38169 19089 3400 29539 17741 31142 4863 21292 602 36320 29219 39678 29801 39741 34695 5748 7115 4508 28940 7092 28896 5822 42660 5552 6050...

result:

ok Accepted.

Test #91:

score: 22

Accepted

time: 207ms

memory: 95644kb

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:

49847 89789 66903 27362 60982 1430 7331 77341 36902 32743 2942 72638 84687 66276 2470 56257 26320 7113 46529 32585 38040 95508 59638 20562 17872 83039 85951 33512 6104 55120 13378 23475 64532 25811 487 65946 23664 54317 85948 39092 74260 45607 80440 83258 68050 42026 33307 83630 20770 97415 16925 38...

result:

ok Accepted.

Test #92:

score: 22

Accepted

time: 214ms

memory: 88472kb

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:

9226 72876 60022 90511 51259 2670 77387 2536 88597 80248 56834 90760 14248 26702 85237 53433 54910 55113 83715 78902 34181 10098 27881 51404 68978 56491 52032 67158 49705 80745 11576 69509 39748 76622 84615 32275 29333 42163 65015 75464 62379 26859 23779 24786 90185 19697 67650 46152 19473 12402 332...

result:

ok Accepted.

Test #93:

score: 22

Accepted

time: 271ms

memory: 135308kb

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:

95952 332274 274624 12112 74566 153299 92577 315395 193707 251682 215555 306887 76649 391122 231246 249187 316437 428817 209951 358199 203428 103217 320573 226053 130659 343749 313577 248208 393999 27085 413202 284635 311076 426216 179905 52999 85198 309082 361759 131729 390733 400437 387810 42095 1...

result:

ok Accepted.

Test #94:

score: 22

Accepted

time: 107ms

memory: 63216kb

input:

output:

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

result:

ok Accepted.

Test #95:

score: 22

Accepted

time: 306ms

memory: 138036kb

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 101912 362351 202943 478091 299458 16456 88290 301357 243418 210276 482564 328420 187424 145851 129852 169359 149505 109977 330924 289678 325165 412681 323621 426775 354692 448692 124569 51883 178132 382369 443140 109076 384652 469350 248302 287365 135382 57456 133656 20575 32801 386581 31184...

result:

ok Accepted.

Test #96:

score: 22

Accepted

time: 285ms

memory: 131448kb

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:

416033 73329 310482 168784 144380 153669 447781 30215 136650 152427 49167 149715 357112 156025 381377 251405 444606 128357 322830 313234 410857 263364 98076 138169 441513 406242 363362 20822 434169 212996 98201 399001 188532 135512 23778 450917 48923 159059 88945 373164 248761 173409 60961 99557 325...

result:

ok Accepted.

Test #97:

score: 22

Accepted

time: 255ms

memory: 131920kb

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:

257541 84446 107101 122560 78681 51857 383725 216412 75444 337655 294097 67643 296650 124306 218378 386016 315389 47523 153187 179223 169683 317228 458961 368939 14695 405911 280684 234515 57814 180416 225797 410774 275739 166414 365807 130808 289869 163704 175880 248299 205970 153394 249265 291192 ...

result:

ok Accepted.

Test #98:

score: 22

Accepted

time: 300ms

memory: 144164kb

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:

420770 190723 222774 428802 481568 338563 108478 270076 399500 381173 331530 437333 91434 253281 389193 163317 214038 315427 242075 313884 18899 135412 462612 208642 33538 395192 308438 30589 75226 386247 464062 170242 475893 122262 427067 129247 1144 6921 417355 12273 160823 257948 203709 211118 71...

result:

ok Accepted.

Test #99:

score: 22

Accepted

time: 293ms

memory: 138872kb

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 386045 142845 395967 148308 390723 115375 326815 949 209247 136337 469694 366001 421503 384161 391258 154225 217834 361487 350730 80915 187447 170091 428385 369033 373761 441483 331477 151903 26513 292015 341057 403172 146096 273525 124250 134810 370470 265635 27984 466715 450061 442027 250556...

result:

ok Accepted.

Test #100:

score: 22

Accepted

time: 62ms

memory: 64008kb

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 458 3 349 21 398 228 310 170 381 341 136 435 122 63 282 402 129 80 195 459 445 172 289 309 169 396 40 368 457 14 75 265 318 190 313 259 377 47 358 340 274 374 192 171 223 103 34 200 82 350 290 423 35 44 391 128 460 94 332 370 239 269 432 369 246 336 268 62 162 191 320 271 473 452 273 209 161 ...

result:

ok Accepted.

Test #101:

score: 22

Accepted

time: 111ms

memory: 63256kb

input:

output:

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

result:

ok Accepted.

Test #102:

score: 22

Accepted

time: 124ms

memory: 61564kb

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:

184 167 203 48 49 33 137 144 10 100 52 130 181 194 20 13 61 89 102 188 209 47 201 101 169 70 92 214 202 177 32 215 39 86 44 79 170 183 97 197 36 50 207 63 58 161 115 109 192 21 136 198 162 69 56 57 6 123 22 213 172 211 168 199 132 210 224 187 30 127 190 16 55 135 228 3 189 219 152 88 205 122 72 31 1...

result:

ok Accepted.

Test #103:

score: 22

Accepted

time: 124ms

memory: 62828kb

input:

output:

94 220 337 374 458 106 33 1 330 266 305 30 69 48 272 322 295 362 320 294 145 353 261 49 142 248 411 118 73 163 57 311 110 355 90 319 77 390 194 329 149 45 81 40 430 378 342 457 98 251 7 293 369 408 165 269 228 406 415 299 285 50 455 95 183 217 47 300 203 63 231 419 348 139 432 243 16 402 58 34 234 4...

result:

ok Accepted.

Test #104:

score: 22

Accepted

time: 122ms

memory: 65964kb

input:

output:

381 168 635 363 905 857 48 121 760 43 875 304 576 922 841 223 6 309 833 137 630 155 408 826 505 633 712 595 459 270 411 729 131 153 21 848 5 497 600 40 340 961 690 715 225 129 770 727 204 207 190 281 958 410 892 667 542 244 681 133 241 150 732 105 450 697 49 886 226 718 18 57 144 562 203 58 517 865 ...

result:

ok Accepted.

Test #105:

score: 22

Accepted

time: 115ms

memory: 66204kb

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:

646 268 511 309 506 97 481 810 157 859 386 873 757 344 856 749 754 61 855 514 457 632 916 44 232 526 84 233 222 591 29 354 275 891 479 485 139 2 949 706 87 763 435 795 952 593 808 547 210 413 290 929 159 683 667 900 367 88 70 20 717 762 935 712 846 122 657 565 945 272 236 310 493 93 168 313 770 545 ...

result:

ok Accepted.

Test #106:

score: 22

Accepted

time: 135ms

memory: 68984kb

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:

3211 3134 339 2694 4175 317 1279 334 1833 967 196 4506 3412 1361 2893 1568 169 4734 224 1016 1404 4564 2538 3372 1589 2840 2594 814 3348 2269 4408 3739 1944 1367 2633 3540 709 572 1622 1675 714 2082 4498 216 1583 826 1858 4111 3747 3752 1683 3633 2531 4107 1593 4523 1071 444 2174 2841 2685 2649 3723...

result:

ok Accepted.

Test #107:

score: 22

Accepted

time: 130ms

memory: 69024kb

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:

597 1703 2445 1159 3896 736 81 1416 196 1333 3855 745 2010 4064 4243 1956 3818 3534 3313 754 867 3817 3348 1756 1002 4381 306 724 2992 4212 3889 22 1790 958 28 2044 417 2057 4461 4333 4339 3833 1420 4128 2322 123 1052 701 2082 1512 3993 3186 1485 2699 118 4257 2520 1270 1900 1162 1293 161 2504 4464 ...

result:

ok Accepted.