QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#424077	#8359. travel	Clonoth	100 ✓	382ms	107560kb	C++20	4.5kb	2024-05-28 21:33:47	2024-05-28 21:33:47

Judging History

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

[2024-05-28 21:33:47]
评测

测评结果：100
用时：382ms
内存：107560kb

查看

[2024-05-28 21:33:47]
提交

answer

#include<stdio.h>
#include<bits/stdc++.h>
#define fir first
#define sec second
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef __int128 int128;
typedef __uint128_t uint128;
typedef pair<int,int> pii;
template<typename type>
inline void chmin(type &x,const type &y)
{
	if(y<x)
		x=y;
}
template<typename type>
inline void chmax(type &x,const type &y)
{
	if(x<y)
		x=y;
}
constexpr int Max=5e5+10;
int opt,n;
ll m;
vector<int>e[Max],o[Max];
int siz[Max],maxn[Max],rt,depth[Max],id[Max],num[Max],fa[Max];
ll L=0,R=0;
void find_rt(int u,int from)
{
	siz[u]=1,maxn[u]=0;
	for(auto v:e[u])
		if(v!=from)
		{
			find_rt(v,u);
			siz[u]+=siz[v];
			chmax(maxn[u],siz[v]);
		}
	chmax(maxn[u],n-siz[u]);
	if(maxn[u]<maxn[rt])
		rt=u;
}
void init(int u,int from,int k)
{
	e[u].erase(find(all(e[u]),from));
	fa[u]=from,depth[u]=depth[from]+1,id[u]=k,siz[u]=1;
	for(auto v:e[u])
		init(v,u,k),siz[u]+=siz[v];
}
vector<int>p[Max],s[Max];
bool tag[Max];
void dfs(int u,int k)
{
	if(u==k)
		s[id[u]].push_back(u);
	p[k].push_back(u);
	for(auto v:e[u])
		dfs(v,tag[v]?k:v);
}
void find(int u,int from)
{
	fa[u]=from;
	for(auto v:e[u])
		if(v!=from)
			depth[v]=depth[u]+1,find(v,u);
}
vector<int>seq;
int pos=0,son[Max];
void dfs1(int u,int from)
{
	fa[u]=from;
	if(!pos&&depth[u]==m)
		pos=u;
	for(auto v:e[u])
		if(v!=from)
		{
			depth[v]=depth[u]+1;
			dfs1(v,u);
		}
}
void dfs2(int u,int from)
{
	if(u!=pos)
		seq.push_back(u);
	for(auto v:e[u])
		if(v!=from&&v!=son[u])
			dfs2(v,u);
	if(son[u])
		dfs2(son[u],u);
}
void solve_diameter()
{
	int S;
	depth[1]=0,fa[1]=0;
	find(1,0);
	S=max_element(depth+1,depth+n+1)-depth;
	depth[S]=0,fa[S]=0;
	m=(n-1)*2-m;
	seq.clear();
	pos=0;
	dfs1(S,0);
	if(!pos)
		cout<<"-1\n";
	else
	{
		for(int i=pos;i!=S;i=fa[i])
			son[fa[i]]=i;
		dfs2(S,0);
		seq.push_back(pos);
		for(auto i:seq)
			cout<<i<<" ";
		cout<<"\n";
	}
}
void solve()
{
	cin>>n>>m>>opt;
	for(int i=1,u,v;i<n;++i)
		cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
	if(opt==1&&m<2*(n-1))
	{
		solve_diameter();
		return;
	}
	if(n==1)
	{
		if(!m)
			cout<<"1\n";
		else
			cout<<"-1\n";
		return;
	}
	if(n==2)
	{
		if(m==opt)
			cout<<"1 2\n";
		else
			cout<<"-1\n";
		return;
	}
	maxn[rt=0]=n;
	find_rt(1,0);
	fa[rt]=0,depth[rt]=0;
	for(auto u:e[rt])
		init(u,rt,u);
	for(int i=1;i<=n;++i)
		R+=depth[i]*2;
	L=R;
	for(int i=1;i<=n;++i)
		L-=2*depth[i]*(ll)e[i].size();
	bool flag=m&1;
	if(opt==1)
		m+=2-flag;
	if(m<L||m>R||((m-L)&1))
	{
		cout<<"-1\n";
		return;
	}
	for(int i=1;i<=n;++i)
		if(fa[i]&&depth[fa[i]])
			o[id[i]].push_back(i);
	priority_queue<pii>Q;
	for(auto u:e[rt])
	{
		sort(all(o[u]),[](const int &x,const int &y)->bool
		{
			return depth[x]<depth[y];
		});
		num[u]=siz[u],Q.emplace(num[u],u);
	}
	m=(R-m)/2;
	while(!Q.empty()&&m>0)
	{
		auto [w,u]=Q.top();
		Q.pop();
		int i=o[u].back(),d=depth[fa[i]];
		if(m>=d)
		{
			m-=d,tag[i]=true;
			o[u].pop_back();
		}
		else
			for(auto i:o[u])
			{
				int d=depth[fa[i]];
				if(m==d)
				{
					m-=d,tag[i]=true;
					break;
				}
			}
		--num[u];
		Q.emplace(num[u],u);
	}
	for(auto u:e[rt])
		dfs(u,u),reverse(all(s[u]));
	p[rt].push_back(rt);
	vector<int>ans;
	ans.push_back(rt);
	while(Q.size()>1)
	{
		auto [w1,u]=Q.top();
		Q.pop();
		auto [w2,v]=Q.top();
		Q.pop();
		--num[u],--num[v];
		ans.push_back(s[u].back());
		s[u].pop_back();
		ans.push_back(s[v].back());
		s[v].pop_back();
		if(num[u])
			Q.emplace(num[u],u);
		if(num[v])
			Q.emplace(num[v],v);
	}
	if(!Q.empty())
	{
		auto [w,u]=Q.top();
		while(w--)
			ans.push_back(s[u].back()),s[u].pop_back();
	}
	int S=0,len=ans.size();
	if(opt==1)
	{
		assert(ans[0]==rt);
		if(flag)
			S=1;
		else
		{
			for(int i=0;i+1<len;++i)
			{
				int u=ans[i],v=ans[i+1];
				if(fa[u]==rt&&fa[v]==rt)
				{
					reverse(all(p[u]));
					S=i+1;
					break;
				}
			}
			assert(S);
		}
	}
	for(int i=0;i<len;++i)
		for(auto j:p[ans[(S+i)%len]])
			cout<<j<<" ";
	cout<<"\n";
}
void clear()
{
	L=R=0;
	for(int i=1;i<=n;++i)
	{
		e[i].clear(),tag[i]=false,p[i].clear(),s[i].clear(),o[i].clear(),num[i]=0;
		siz[i]=0,id[i]=0,num[i]=0,son[i]=0;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int t;
	cin>>t;
	for(int i=1;i<=t;++i)
		solve(),clear();
	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: 2ms

memory: 3824kb

input:

output:

result:

ok Accepted.

Subtask #2:

score: 4

Accepted

Test #2:

score: 4

Accepted

time: 0ms

memory: 15964kb

input:

output:

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

result:

ok Accepted.

Test #3:

score: 4

Accepted

time: 4ms

memory: 18012kb

input:

output:

1 6 7 8 2 5 9 3 4 
6 7 8 9 2 3 4 5 1 
5 4 3 2 1 9 8 7 6 
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: 0ms

memory: 15928kb

input:

output:

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

result:

ok Accepted.

Test #5:

score: 4

Accepted

time: 4ms

memory: 15904kb

input:

output:

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

result:

ok Accepted.

Test #6:

score: 4

Accepted

time: 3ms

memory: 15924kb

input:

output:

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

result:

ok Accepted.

Test #7:

score: 4

Accepted

time: 0ms

memory: 16164kb

input:

output:

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

result:

ok Accepted.

Test #8:

score: 4

Accepted

time: 0ms

memory: 12016kb

input:

output:

result:

ok Accepted.

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #9:

score: 8

Accepted

time: 0ms

memory: 17920kb

input:

output:

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

result:

ok Accepted.

Test #10:

score: 8

Accepted

time: 2ms

memory: 17916kb

input:

output:

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

result:

ok Accepted.

Test #11:

score: 8

Accepted

time: 0ms

memory: 18212kb

input:

output:

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

result:

ok Accepted.

Test #12:

score: 8

Accepted

time: 5ms

memory: 17924kb

input:

output:

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

result:

ok Accepted.

Test #13:

score: 8

Accepted

time: 0ms

memory: 16160kb

input:

output:

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

result:

ok Accepted.

Test #14:

score: 8

Accepted

time: 5ms

memory: 15868kb

input:

output:

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

result:

ok Accepted.

Test #15:

score: 8

Accepted

time: 0ms

memory: 12052kb

input:

output:

result:

ok Accepted.

Subtask #4:

score: 14

Accepted

Test #16:

score: 14

Accepted

time: 0ms

memory: 16176kb

input:

output:

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

result:

ok Accepted.

Test #17:

score: 14

Accepted

time: 4ms

memory: 13888kb

input:

output:

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

result:

ok Accepted.

Test #18:

score: 14

Accepted

time: 0ms

memory: 11804kb

input:

output:

result:

ok Accepted.

Test #19:

score: 14

Accepted

time: 0ms

memory: 15952kb

input:

output:

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

result:

ok Accepted.

Test #20:

score: 14

Accepted

time: 0ms

memory: 17952kb

input:

output:

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

result:

ok Accepted.

Test #21:

score: 14

Accepted

time: 4ms

memory: 14160kb

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

memory: 18300kb

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:

190 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 ...

result:

ok Accepted.

Test #23:

score: 14

Accepted

time: 5ms

memory: 18268kb

input:

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

output:

969 967 970 966 971 965 972 964 973 963 974 962 975 961 976 960 977 959 978 958 979 957 980 956 981 955 982 954 983 953 984 952 985 951 986 950 987 949 988 948 989 947 990 946 991 945 992 944 993 943 994 942 995 941 996 940 997 939 998 938 999 937 1000 936 1001 935 1002 934 1003 933 1004 932 1005 93...

result:

ok Accepted.

Test #24:

score: 14

Accepted

time: 0ms

memory: 18196kb

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:

960 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 102...

result:

ok Accepted.

Test #25:

score: 14

Accepted

time: 0ms

memory: 18352kb

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:

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

result:

ok Accepted.

Test #26:

score: 14

Accepted

time: 0ms

memory: 18260kb

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:

928 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 ...

result:

ok Accepted.

Subtask #5:

score: 10

Accepted

Dependency #4:

100%

Accepted

Test #27:

score: 10

Accepted

time: 64ms

memory: 11708kb

input:

output:

result:

ok Accepted.

Test #28:

score: 10

Accepted

time: 108ms

memory: 39248kb

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:

46523 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 ...

result:

ok Accepted.

Test #29:

score: 10

Accepted

time: 114ms

memory: 88972kb

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:

240925 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...

result:

ok Accepted.

Test #30:

score: 10

Accepted

time: 139ms

memory: 107560kb

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:

247381 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...

result:

ok Accepted.

Test #31:

score: 10

Accepted

time: 129ms

memory: 106392kb

input:

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

output:

245324 245322 245325 245321 245326 245320 245327 245319 245328 245318 245329 245317 245330 245316 245331 245315 245332 245314 245333 245313 245334 245312 245335 245311 245336 245310 245337 245309 245338 245308 245339 245307 245340 245306 245341 245305 245342 245304 245343 245303 245344 245302 245345...

result:

ok Accepted.

Test #32:

score: 10

Accepted

time: 138ms

memory: 105552kb

input:

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

output:

228006 228008 228005 228009 228004 228010 228003 228011 228002 228012 228001 228013 228000 228014 227999 228015 227998 228016 227997 228017 227996 228018 227995 228019 227994 228020 227993 228021 227992 228022 227991 228023 227990 228024 227989 228025 227988 228026 227987 228027 227986 228028 227985...

result:

ok Accepted.

Test #33:

score: 10

Accepted

time: 51ms

memory: 17968kb

input:

output:

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 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 
-1
-1
-1
49 46...

result:

ok Accepted.

Test #34:

score: 10

Accepted

time: 67ms

memory: 17924kb

input:

output:

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

result:

ok Accepted.

Test #35:

score: 10

Accepted

time: 79ms

memory: 15984kb

input:

output:

117 115 118 114 113 119 112 120 111 121 110 122 109 123 108 124 107 125 106 126 105 127 104 128 103 129 102 130 101 131 100 132 99 133 98 134 97 135 96 136 95 137 94 138 93 139 92 140 91 141 90 142 89 143 88 144 87 145 86 146 85 147 84 148 83 149 82 150 81 151 80 152 79 153 78 154 77 155 76 156 75 1...

result:

ok Accepted.

Test #36:

score: 10

Accepted

time: 85ms

memory: 20864kb

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:

1212 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 ...

result:

ok Accepted.

Test #37:

score: 10

Accepted

time: 80ms

memory: 21824kb

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:

4584 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 ...

result:

ok Accepted.

Test #38:

score: 10

Accepted

time: 91ms

memory: 26176kb

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:

12052 12054 12051 12055 12050 12056 12049 12057 12048 12058 12047 12059 12046 12060 12045 12061 12044 12062 12043 12063 12042 12064 12041 12065 12040 12066 12039 12067 12038 12068 12037 12069 12036 12070 12035 12071 12034 12072 12033 12073 12032 12074 12031 12075 12030 12076 12029 12077 12028 12078 ...

result:

ok Accepted.

Test #39:

score: 10

Accepted

time: 98ms

memory: 31732kb

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:

24169 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 ...

result:

ok Accepted.

Test #40:

score: 10

Accepted

time: 84ms

memory: 31028kb

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:

24207 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 ...

result:

ok Accepted.

Test #41:

score: 10

Accepted

time: 104ms

memory: 40752kb

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:

45597 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 ...

result:

ok Accepted.

Subtask #6:

score: 12

Accepted

Dependency #3:

100%

Accepted

Test #42:

score: 12

Accepted

time: 0ms

memory: 17916kb

input:

output:

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

result:

ok Accepted.

Test #43:

score: 12

Accepted

time: 0ms

memory: 15932kb

input:

output:

-1
-1
5 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 
-1
-1

result:

ok Accepted.

Test #44:

score: 12

Accepted

time: 0ms

memory: 13800kb

input:

output:

result:

ok Accepted.

Test #45:

score: 12

Accepted

time: 0ms

memory: 18176kb

input:

output:

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

result:

ok Accepted.

Test #46:

score: 12

Accepted

time: 2ms

memory: 17972kb

input:

output:

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

result:

ok Accepted.

Test #47:

score: 12

Accepted

time: 4ms

memory: 18212kb

input:

output:

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

result:

ok Accepted.

Test #48:

score: 12

Accepted

time: 0ms

memory: 17916kb

input:

output:

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

result:

ok Accepted.

Test #49:

score: 12

Accepted

time: 0ms

memory: 17984kb

input:

output:

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

result:

ok Accepted.

Test #50:

score: 12

Accepted

time: 0ms

memory: 17924kb

input:

output:

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

result:

ok Accepted.

Test #51:

score: 12

Accepted

time: 5ms

memory: 17980kb

input:

output:

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

result:

ok Accepted.

Test #52:

score: 12

Accepted

time: 4ms

memory: 16160kb

input:

output:

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

result:

ok Accepted.

Subtask #7:

score: 18

Accepted

Dependency #4:

100%

Accepted

Dependency #6:

100%

Accepted

Test #53:

score: 18

Accepted

time: 4ms

memory: 13808kb

input:

output:

result:

ok Accepted.

Test #54:

score: 18

Accepted

time: 0ms

memory: 18052kb

input:

output:

24 264 21 365 171 47 122 151 343 42 173 75 138 351 39 242 250 74 202 26 348 65 206 121 233 312 70 320 110 8 83 276 218 118 48 275 287 161 339 106 27 105 342 155 111 140 278 341 290 199 148 77 174 81 76 19 196 90 228 172 186 167 102 260 367 61 153 335 359 108 347 179 104 133 268 297 64 114 267 223 30...

result:

ok Accepted.

Test #55:

score: 18

Accepted

time: 4ms

memory: 18248kb

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:

1383 1215 1196 1257 1382 1974 1224 878 28 191 1426 555 1344 245 1303 1744 723 695 767 1931 167 1295 433 1718 368 1875 687 852 1097 1700 1137 1228 1633 1100 1534 906 435 886 1688 287 1738 1199 960 472 1979 1094 1214 1906 224 550 1236 1048 1351 289 1928 790 1184 453 1616 896 1886 507 220 920 869 877 1...

result:

ok Accepted.

Test #56:

score: 18

Accepted

time: 2ms

memory: 18148kb

input:

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

output:

430 151 1493 1825 1898 1530 1360 1617 1880 865 828 522 128 1757 225 569 867 1492 1070 369 886 1293 27 212 1511 1804 399 1101 270 967 1570 636 341 605 1832 155 885 1956 215 550 1481 1338 1576 1363 181 1501 713 1377 689 1515 20 49 99 1909 409 1500 1863 3 1386 1341 500 1335 966 466 1183 947 665 1661 10...

result:

ok Accepted.

Test #57:

score: 18

Accepted

time: 0ms

memory: 18272kb

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:

179 1272 1527 735 1862 691 176 1565 212 201 1365 153 1086 1806 1761 1535 1120 792 1361 702 89 243 674 217 1262 863 1089 1122 877 968 388 1642 1792 1743 88 1065 1421 1391 1463 1357 1101 940 86 616 54 306 1048 1807 928 1865 835 383 159 214 1608 1588 1102 1093 349 26 1724 1469 1218 1869 1505 1011 979 1...

result:

ok Accepted.

Test #58:

score: 18

Accepted

time: 5ms

memory: 18208kb

input:

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

output:

784 796 249 85 870 690 1161 1830 1525 1219 1644 14 1685 1062 843 1405 765 244 1060 176 1693 638 1250 785 884 503 1141 418 115 779 787 945 538 220 86 95 1317 426 609 642 1593 236 1323 484 1468 702 191 299 390 1137 233 1363 975 228 472 1802 1125 1016 1307 1086 420 986 963 460 206 946 303 565 1552 517 ...

result:

ok Accepted.

Test #59:

score: 18

Accepted

time: 2ms

memory: 13876kb

input:

output:

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

result:

ok Accepted.

Test #60:

score: 18

Accepted

time: 4ms

memory: 16160kb

input:

output:

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

result:

ok Accepted.

Test #61:

score: 18

Accepted

time: 0ms

memory: 15820kb

input:

output:

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

result:

ok Accepted.

Test #62:

score: 18

Accepted

time: 4ms

memory: 17916kb

input:

output:

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

result:

ok Accepted.

Test #63:

score: 18

Accepted

time: 5ms

memory: 18240kb

input:

output:

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

result:

ok Accepted.

Test #64:

score: 18

Accepted

time: 0ms

memory: 15908kb

input:

output:

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

result:

ok Accepted.

Test #65:

score: 18

Accepted

time: 4ms

memory: 17900kb

input:

output:

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

result:

ok Accepted.

Test #66:

score: 18

Accepted

time: 0ms

memory: 17992kb

input:

output:

349 28 74 346 239 90 91 61 370 66 257 179 186 305 195 120 222 6 282 354 75 343 336 190 164 177 358 110 18 279 335 129 380 165 187 62 93 119 114 178 263 97 329 10 192 312 213 325 221 246 103 265 320 290 310 63 159 36 235 71 345 374 330 243 258 234 210 169 291 207 359 1 146 135 362 54 377 172 230 284 ...

result:

ok Accepted.

Test #67:

score: 18

Accepted

time: 4ms

memory: 18288kb

input:

output:

174 371 24 156 99 219 71 293 8 14 65 348 138 38 115 169 133 102 164 193 362 188 266 206 286 72 131 231 374 324 364 9 296 191 278 297 104 114 237 60 338 225 5 61 31 302 89 113 119 84 15 147 3 36 350 64 177 93 322 369 59 221 58 141 194 44 260 70 243 40 370 179 27 342 1 176 26 139 184 187 170 195 341 1...

result:

ok Accepted.

Subtask #8:

score: 10

Accepted

Dependency #7:

100%

Accepted

Test #68:

score: 10

Accepted

time: 15ms

memory: 9732kb

input:

output:

result:

ok Accepted.

Test #69:

score: 10

Accepted

time: 24ms

memory: 19676kb

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:

4176 2520 3761 1800 3180 4642 4465 2557 599 1749 4242 2870 2111 4179 1149 2987 901 2925 2262 2106 553 736 1590 4710 3076 182 3461 302 1319 1851 4729 1501 4537 4 426 748 3528 104 4632 2263 4234 2168 1747 2859 2482 4616 2013 3255 540 194 3536 1344 2421 3321 3287 1804 4500 3920 947 3860 4057 3571 4690 ...

result:

ok Accepted.

Test #70:

score: 10

Accepted

time: 22ms

memory: 18380kb

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:

6531 8467 9562 1384 4274 5964 50 899 456 3080 9208 6799 6883 1515 41 674 2898 5028 1790 1901 4853 6796 2095 7940 4863 6017 7815 6725 90 8108 1630 9085 1510 3819 9634 2745 5142 8676 5626 5271 4996 2682 2609 7821 8575 1334 2185 6026 1601 6140 1604 7052 7780 5657 2865 3440 676 8525 6740 8094 590 5720 9...

result:

ok Accepted.

Test #71:

score: 10

Accepted

time: 33ms

memory: 19744kb

input:

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

output:

17055 4611 3728 10372 6908 18220 5359 10844 13306 10201 6335 4413 17412 4692 18219 13490 16489 4567 10850 17267 15815 4257 6096 3257 14793 5164 17559 11651 13232 462 6145 4414 14095 6137 13120 434 8332 927 15816 10527 13066 13300 18013 5453 553 4994 140 15574 6611 15136 12680 635 16605 15899 2805 11...

result:

ok Accepted.

Test #72:

score: 10

Accepted

time: 33ms

memory: 21848kb

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:

23689 14547 12874 25551 26413 31139 5967 11904 26556 3227 24862 20114 8404 15317 28189 18909 762 18799 6083 2572 8348 8203 25420 23941 7318 6202 30556 1977 21317 2762 25153 899 29871 26972 29069 27490 31225 21808 29156 18993 7518 8966 4516 15054 14642 22845 27033 28422 20736 5282 26124 23863 6246 29...

result:

ok Accepted.

Test #73:

score: 10

Accepted

time: 48ms

memory: 21800kb

input:

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

output:

16122 17937 11926 26971 4620 17222 14112 2338 24424 5544 18983 14806 6684 28078 4859 19125 21544 11022 13518 32153 18816 19830 10967 2057 22761 4881 14912 1993 22514 11352 24344 28155 19922 4442 32302 12677 16760 19654 14025 7517 11268 14474 31271 30830 23403 21155 10332 8340 27530 24681 29770 14702...

result:

ok Accepted.

Test #74:

score: 10

Accepted

time: 17ms

memory: 16120kb

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
42 201 148 216 180 226 210 135 275 290 13 209 348 302 32 190 327 186 306 158 182 320 377 106 55 78 25 220 271 39 195 52 248 286 370 278 355 156 225 318 301 155 197 34 123 312 191 79 122 378 14 309 280 363 60 357 68 41 88 165 5 76 192 23 358 176 360 134 35 366 3...

result:

ok Accepted.

Test #75:

score: 10

Accepted

time: 19ms

memory: 18148kb

input:

output:

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

result:

ok Accepted.

Test #76:

score: 10

Accepted

time: 20ms

memory: 17936kb

input:

output:

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

result:

ok Accepted.

Test #77:

score: 10

Accepted

time: 18ms

memory: 17956kb

input:

output:

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

result:

ok Accepted.

Test #78:

score: 10

Accepted

time: 19ms

memory: 18096kb

input:

output:

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

result:

ok Accepted.

Test #79:

score: 10

Accepted

time: 20ms

memory: 16188kb

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:

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

result:

ok Accepted.

Test #80:

score: 10

Accepted

time: 22ms

memory: 18664kb

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:

382 471 387 150 26 133 306 92 255 288 42 9 104 91 14 316 455 203 436 60 29 348 121 27 168 164 4 379 229 108 369 424 89 284 271 160 1 206 101 32 126 363 71 119 390 459 432 427 52 139 457 198 355 251 69 13 114 328 383 318 156 465 143 234 470 296 191 262 397 422 297 460 267 226 116 38 323 62 252 340 43...

result:

ok Accepted.

Test #81:

score: 10

Accepted

time: 21ms

memory: 18912kb

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:

878 937 932 257 114 821 555 952 839 158 484 613 551 586 395 92 356 739 258 14 872 697 659 449 175 121 188 848 810 122 955 222 558 351 896 954 458 372 582 422 690 70 326 972 911 874 894 29 482 147 834 701 554 912 302 945 104 614 801 910 172 74 644 272 827 345 235 883 254 793 657 234 537 141 734 136 7...

result:

ok Accepted.

Test #82:

score: 10

Accepted

time: 24ms

memory: 19132kb

input:

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

output:

833 1600 467 1714 580 1610 1127 102 1223 1754 1071 1114 1161 160 854 1724 257 697 11 10 878 568 1170 313 985 133 1330 465 1374 780 333 1105 889 1750 1642 590 734 31 829 1838 529 356 531 651 459 1291 737 1191 1609 315 220 592 1009 123 218 857 773 1472 1835 1095 584 1686 611 1654 1496 721 296 68 199 1...

result:

ok Accepted.

Subtask #9:

score: 22

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Dependency #8:

100%

Accepted

Test #83:

score: 22

Accepted

time: 59ms

memory: 11768kb

input:

output:

result:

ok Accepted.

Test #84:

score: 22

Accepted

time: 114ms

memory: 22008kb

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:

4138 2393 192 1286 2788 4126 4666 2231 4542 3407 1811 1167 968 1418 2388 1852 2965 4245 2576 4072 3312 3542 2781 2428 393 2104 3884 361 4268 1057 3093 559 2567 376 1068 2654 3512 1042 3649 1586 3603 2417 466 693 1034 2680 2380 4535 999 2855 1460 3501 4222 3178 4864 2940 4378 1433 191 3205 2784 4483 ...

result:

ok Accepted.

Test #85:

score: 22

Accepted

time: 132ms

memory: 24216kb

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:

3703 7377 2153 331 3530 8429 5719 3922 7039 7289 8379 5942 7493 4986 7601 8717 5226 540 7739 2034 3536 3826 7727 6627 8448 3072 356 4166 9055 8140 3606 6217 3070 7410 4543 7507 2290 1362 9192 5852 2774 8492 7894 843 9260 6103 5436 845 7767 1863 8002 1012 7325 2834 3332 3228 237 7832 4930 7470 4518 6...

result:

ok Accepted.

Test #86:

score: 22

Accepted

time: 140ms

memory: 22128kb

input:

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

output:

5717 5559 2581 8930 7334 2378 851 1978 2515 6597 4002 5536 7376 3899 5659 8923 9366 3629 7612 159 5780 5721 655 3724 7272 4052 3359 1895 5432 9033 6351 2941 1275 1342 7059 1272 9183 1509 4639 5877 1156 6563 4813 3805 5818 4571 8264 9166 7852 3962 4990 7686 206 7742 4783 8254 5592 4458 3172 77 1738 1...

result:

ok Accepted.

Test #87:

score: 22

Accepted

time: 169ms

memory: 25956kb

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:

3593 12777 10911 11473 7353 6665 9084 4657 3713 7597 5825 3346 3578 18256 1576 15568 10794 17256 278 15945 4496 17667 17830 971 9853 17070 17135 13447 17151 18661 9518 16364 11464 8998 16910 1578 16446 6228 12387 12665 11135 12813 13239 12992 10878 17413 7346 12469 1006 15202 19540 16620 18435 11644...

result:

ok Accepted.

Test #88:

score: 22

Accepted

time: 172ms

memory: 25580kb

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:

12748 6648 13968 890 7029 2948 964 14579 10738 6538 10813 13172 13202 3718 13247 17839 852 12856 9644 10767 5262 1513 16623 8178 6589 7576 11687 16221 19750 14385 8689 13923 1004 1160 13858 3973 1600 5126 17933 13065 2977 16162 18344 8952 17408 13295 19244 1209 1720 14508 16196 6036 11498 4348 8280 ...

result:

ok Accepted.

Test #89:

score: 22

Accepted

time: 206ms

memory: 30236kb

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:

47561 38337 29006 46412 30821 20515 24014 3296 42620 37473 28124 22777 21270 1570 24488 18111 16456 205 1188 1017 37509 30207 2552 4990 32194 29546 28461 43899 15427 18310 27485 38402 31181 12622 46402 3959 28063 47407 5440 33481 10 12724 5030 2704 30895 370 19056 46432 19843 22916 39453 11598 10577...

result:

ok Accepted.

Test #90:

score: 22

Accepted

time: 190ms

memory: 29788kb

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 36902 23697 43546 10902 8727 17679 6901 35083 31818 16537 32364 21349 10030 11420 5484 12835 37490 22402 44046 6026 17181 32903 41489 29934 33470 1762 5848 35554 2491 36718 38219 30032 30279 24287 2257 42373 45127 30078 6775 20762 18255 36999 12935 2346 14240 13968 38283 21716 7686 11317 44458 ...

result:

ok Accepted.

Test #91:

score: 22

Accepted

time: 212ms

memory: 37676kb

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:

54951 49847 89789 66903 996 60982 66774 7331 53567 35438 67628 31238 22880 36902 71776 23328 27362 2942 95951 84687 1430 30530 77341 78199 32743 2470 72638 26320 66276 46529 56257 38040 7113 59638 91005 57826 3393 17872 32585 85951 95508 6104 20562 13378 83039 64532 33512 487 55120 91675 46032 23664...

result:

ok Accepted.

Test #92:

score: 22

Accepted

time: 212ms

memory: 37816kb

input:

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

output:

45523 22901 59867 60022 72876 41426 16399 30277 2670 20991 90511 1790 64140 45650 2536 4407 78949 56834 80248 88597 90760 51259 60676 77387 78902 42183 55113 17382 53433 69312 26702 85237 75310 14248 42435 57835 33321 23960 79280 77029 76622 42658 69509 60159 80745 5655 51404 29696 10098 54910 67158...

result:

ok Accepted.

Test #93:

score: 22

Accepted

time: 358ms

memory: 88432kb

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:

250496 323822 332274 223344 12112 274624 153299 215140 307517 74566 251682 71311 315395 200508 276727 423010 306887 315419 276339 100123 244456 92577 404545 9119 469314 129612 64541 116709 220816 117984 124929 193707 249187 162736 391122 286628 107679 203428 68102 209951 316666 215555 428817 316437 ...

result:

ok Accepted.

Test #94:

score: 22

Accepted

time: 91ms

memory: 17864kb

input:

output:

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

result:

ok Accepted.

Test #95:

score: 22

Accepted

time: 372ms

memory: 91112kb

input:

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

output:

181682 4466 254546 132617 299458 362351 202943 466268 72760 478091 243418 342377 88290 568 338407 216903 482564 51013 438309 400717 39039 432277 328160 19874 360879 77750 391454 29864 385056 16456 129852 293591 187424 267168 5850 454518 88483 441032 17298 210276 35318 301357 149505 280810 364174 441...

result:

ok Accepted.

Test #96:

score: 22

Accepted

time: 358ms

memory: 87112kb

input:

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

output:

445753 86698 312653 140264 168861 158300 164878 46619 159222 32858 73329 447781 193384 144380 220207 310482 153669 280537 168784 75967 257215 381377 30215 49167 149715 136650 152427 357112 318660 451102 156025 232264 350992 138606 251405 78386 55723 444606 414889 352797 143076 158410 313234 417827 1...

result:

ok Accepted.

Test #97:

score: 22

Accepted

time: 347ms

memory: 83968kb

input:

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

output:

353265 397678 54498 210413 331365 245542 149316 258351 400721 107101 147191 438321 84446 393642 76518 78681 166955 272366 216412 372517 51857 382783 122560 388654 384930 383725 317731 75444 65361 80377 343504 421037 247747 15878 195692 341856 337655 325200 81332 175369 342122 123807 67643 71615 2887...

result:

ok Accepted.

Test #98:

score: 22

Accepted

time: 365ms

memory: 95064kb

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:

271472 420770 190723 222774 13596 96017 7632 287748 428802 192249 338563 65084 270076 481568 364347 108478 386445 399500 381173 379984 437333 331530 311031 439971 461538 294512 64039 91434 67730 389193 3700 214038 253281 428319 163317 243995 315427 7248 313884 242075 350026 18899 227534 462612 13541...

result:

ok Accepted.

Test #99:

score: 22

Accepted

time: 382ms

memory: 89176kb

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:

260795 76397 386045 142845 86254 148308 395967 115375 390723 949 340436 152786 72161 136337 326815 366001 209247 384161 469694 154225 421503 361487 391258 80915 217834 345618 350730 170091 118596 211379 19477 369033 382537 441483 189769 392642 426133 118977 173006 211027 83632 151903 275273 292015 1...

result:

ok Accepted.

Test #100:

score: 22

Accepted

time: 67ms

memory: 16768kb

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 228 252 3 349 21 322 176 298 477 415 341 398 170 136 63 310 435 381 359 129 402 282 281 122 80 441 459 61 461 52 172 221 137 445 397 195 327 373 309 315 226 169 455 289 140 264 292 40 259 29 190 329 368 377 396 457 14 313 265 318 142 75 147 364 213 352 363 358 219 285 448 163 233 468 45 272 3...

result:

ok Accepted.

Test #101:

score: 22

Accepted

time: 90ms

memory: 17956kb

input:

output:

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

result:

ok Accepted.

Test #102:

score: 22

Accepted

time: 102ms

memory: 18652kb

input:

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

output:

166 15 167 26 200 90 48 42 40 203 47 84 188 154 89 7 13 218 144 49 33 186 194 137 100 9 130 43 148 106 138 54 101 34 70 107 191 119 126 164 145 174 214 71 177 171 83 95 93 133 215 78 221 51 125 220 105 227 64 81 180 121 183 170 79 44 86 39 197 52 59 10 17 32 28 202 104 181 38 92 169 85 20 75 209 143...

result:

ok Accepted.

Test #103:

score: 22

Accepted

time: 107ms

memory: 21460kb

input:

output:

94 235 345 337 374 349 106 101 386 458 1 460 48 428 30 330 266 33 276 305 322 222 6 69 358 445 362 272 260 398 353 295 294 320 421 182 49 270 93 261 176 145 99 124 224 249 248 142 19 411 275 90 103 110 118 73 332 57 163 229 250 194 454 77 311 202 258 5 267 137 355 149 390 81 319 230 365 357 221 24 3...

result:

ok Accepted.

Test #104:

score: 22

Accepted

time: 104ms

memory: 21092kb

input:

output:

971 422 333 635 803 935 628 251 893 931 20 421 771 905 272 794 643 765 559 701 625 857 143 363 465 769 713 963 48 121 134 43 123 285 608 700 522 130 110 304 415 375 760 490 827 644 137 841 309 630 875 833 223 6 576 260 922 373 504 674 463 408 514 210 155 135 675 924 710 457 510 198 551 325 672 201 6...

result:

ok Accepted.

Test #105:

score: 22

Accepted

time: 105ms

memory: 21104kb

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:

571 646 268 387 318 112 309 511 960 506 115 481 739 872 97 936 810 869 859 157 873 386 55 757 344 856 749 754 61 855 514 457 632 916 44 232 526 756 398 84 737 222 233 29 591 275 277 479 658 80 128 172 354 190 891 139 485 823 2 949 706 87 332 435 763 952 795 808 593 210 547 290 413 159 929 667 294 36...

result:

ok Accepted.

Test #106:

score: 22

Accepted

time: 116ms

memory: 24032kb

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:

1322 3211 3134 339 764 4175 2694 1279 317 1594 334 4203 967 3204 3249 4009 4506 290 1361 2793 2521 3773 1568 1833 534 196 2863 4146 4727 1020 4734 4159 1016 1921 2509 2087 2210 3412 545 2917 1005 2893 2453 169 4564 2083 3372 2260 2840 3258 814 4063 2269 224 217 1404 3739 2538 1367 3410 1530 751 2896...

result:

ok Accepted.

Test #107:

score: 22

Accepted

time: 119ms

memory: 23896kb

input:

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

output:

666 3832 1416 1138 736 2445 1159 652 1819 3197 1788 3896 1897 2732 4100 4308 1663 49 1333 81 745 196 606 1064 1756 4011 3817 2249 754 3855 3534 1494 4064 2010 1956 3913 498 4091 1666 1265 3883 1970 1809 4243 4381 867 3048 3818 4106 3313 2288 3622 3906 3954 724 3353 943 1196 3174 2239 1507 3348 3207 ...

result:

ok Accepted.