QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#716265	#9251. Graph Changing	ZhongNi	AC ✓	151ms	3692kb	C++14	3.3kb	2024-11-06 14:47:32	2024-11-06 14:47:34

Judging History

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

[2024-11-06 14:47:34]
评测

测评结果：AC
用时：151ms
内存：3692kb

查看

[2024-11-06 14:47:32]
提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void write(int k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		write(k/10);
	putchar(k%10+'0');
}
/*
直接按照k的大小讨论
k=1是平凡的,一次操作之后是完全图,然后就一直是空图
当2*k>=n的时候,每个i会连一个后缀,然后前面不互相连,后面不互相连
然后会发现当k>=4的时候,操作完一次之后就是空图了
讨论当k=2和3的时候,发现n很小,暴力判断就行了
当2*k<n的时候,k=2就是先是只连一个后缀,再是只连后面k个,循环
k=3时,连了一次之后1~n-2*k全部都要删去,然后就是一个2*k<=n的问题
k>=4连了一次之后就是空图
*/
int q,n,k,t,x,y;
void solve(){
	if(k>=4){
		if(t>1)
			write(-1);
		else if(t==1){
			if(y<n-k+1)
				write(2);
			else if(x>k)
				write(2);
			else if(y-x>=k)
				write(1);
			else if(x<n-k+1&&y>k)
				write(3);
			else
				write(-1);
		}
		else
			write(y-x);
	}
	else if(k==3){
		if(n==2||n==3)
			write(t?-1:y-x);
		else if(n==4){
			if(t==1&&x==1&&y==4)
				write(1);
			else
				write(t?-1:y-x);
		}
		else if(n==5){
			if(!t)
				write(y-x);
			else if(t==1){
				if(x==3||y==3)
					write(-1);
				else if(x==1)
					write(y==2?2:1);
				else if(x==2)
					write(y==4?3:1);
				else if(x==4)
					write(2);
			}
			else if(t==2)
				write(x==2&&y==4?1:-1);
			else
				write(-1);
		}
		else{
			if(!t)
				write(y-x);
			else if(t==1){
				if(x==1)
					write(y<=3?2:1);
				else if(x==2)
					write(y==3?2:(y==4?3:1));
				else if(x==3)
					write(y<=5?3:1);
				else if(x==4||x==5)
					write(2);
			}
			else if(t==2){
				if(x==1||y==6)
					write(-1);
				else if(x==2)
					write(y==3?2:(y==4?1:3));
				else if(x==3)
					write(1);
				else
					write(2);
			}
			else if(t==3)
				write(x==2&&y==5?1:-1);
			else
				write(-1);
		}
	}
	else{
		if(n==2)
			write(t?-1:y-x);
		else if(n==3){
			if(!t)
				write(y-x);
			else if(t==1)
				write(x==1&&y==3?1:-1);
			else
				write(-1);
		}
		else if(n==4){
			if(!(t&1))
				write(y-x);
			else{
				if(x==1)
					write(y==2?2:1);
				else if(x==2)
					write(y==3?3:1);
				else if(x==3)
					write(2);
			}
		}
	}
}
int main(){
	// freopen("graph.in","r",stdin);
	// freopen("graph.out","w",stdout);
	q=read();
	while(q--){
		t=read();
		n=read();
		k=read();
		x=read();
		y=read();
		if(x>y)
			swap(x,y);
		if(k==1){
			if(t>=1)
				write(1);
			else
				write(y-x);
		}
		else if(2*k>=n)
			solve();
		else{
			if(!t)
				write(y-x);
			else if(t==1){
				if(y>=x+k)
					write(1);
				else if(y>n-k&&x<k+1)
					write(3);
				else
					write(2);
			}
			else if(k==2){
				if(!(t&1))
					write((y-x)/(k-1));
				else{
					if(y>=x+k)
						write(1);
					else if(y>n-k&&x<k+1)
						write(3);
					else
						write(2);
				}
			}
			else if(k==3){
				if(t==2&&x<k+1&&y>n-k&&y<x+k)
					write(1);
				else
					write(-1);
			}
			else
				write(-1);
		}
		putchar('\n');
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3632kb

input:

output:

result:

ok 5 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

output:

1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1

result:

ok 30 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

output:

1
1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 90 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

output:

1
1
1
1
1
1
2
1
1
3
1
2
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
1
2
3
1
2
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
2
1
1
3
1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
1...

result:

ok 180 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

output:

1
1
1
1
1
1
1
1
1
1
2
1
1
1
2
1
1
2
1
2
2
-1
1
1
-1
3
1
-1
-1
2
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
1
2
3
1
2
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300 lines

Test #6:

score: 0

Accepted

time: 0ms

memory: 3564kb

input:

output:

result:

ok 450 lines

Test #7:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

output:

result:

ok 630 lines

Test #8:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

output:

result:

ok 840 lines

Test #9:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

output:

result:

ok 1080 lines

Test #10:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

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

output:

result:

ok 1350 lines

Test #11:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

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

output:

result:

ok 1650 lines

Test #12:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

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

output:

result:

ok 1980 lines

Test #13:

score: 0

Accepted

time: 0ms

memory: 3688kb

input:

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

output:

result:

ok 2340 lines

Test #14:

score: 0

Accepted

time: 143ms

memory: 3532kb

input:

1000000
247642294 961448649 733001129 279130562 530835402
732002655 505705299 645705556 487588093 488005936
423909487 956469930 42118321 776825480 857914491
573024322 173584499 411922860 68071790 127760171
195256403 617390756 240978977 289616458 604023215
302970816 281642201 617886109 245587163 2738...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000000 lines

Test #15:

score: 0

Accepted

time: 142ms

memory: 3560kb

input:

999999
818561732 105393047 308277328 55828222 95820891
626623416 914227808 963423453 365760112 463062746
685116026 447528560 848245265 304903588 410888549
190989264 573411702 351364570 477139815 538078040
165251011 443239658 880597903 283340857 321622039
580345373 729628729 253275172 260647549 56083...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 999999 lines

Test #16:

score: 0

Accepted

time: 147ms

memory: 3652kb

input:

999998
641304551 95615249 714496774 44706863 82597067
99120825 296948618 325272169 221497167 253219866
547135214 407423323 615477879 395311431 402237613
902423318 562586582 197117012 215866474 332581531
746228275 461110170 365490393 8270545 13567149
209099954 601749155 822593415 70976179 302958983
7...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 999998 lines

Test #17:

score: 0

Accepted

time: 151ms

memory: 3628kb

input:

999997
759014662 790870149 120716220 312341665 750583643
908054724 384702127 982088181 220708338 372080663
745590890 662285387 822901980 14637938 407944387
613857370 473613609 192612558 314642869 447537089
327205537 773947983 850382884 367385950 465660605
542887244 473869581 242168554 442534885 4616...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 999997 lines

Test #18:

score: 0

Accepted

time: 143ms

memory: 3568kb

input:

999996
286790189 76059652 676678771 27025196 72899785
380552134 140538090 638904193 140356967 140371077
944046566 622180150 180069186 386081350 473991190
325291423 167821189 333332295 37470414 135098524
834553872 8637942 335275375 984215 5958852
245270753 51022707 516519501 15376414 50059575
4736168...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 999996 lines

Test #19:

score: 0

Accepted

time: 116ms

memory: 3688kb

input:

1000000
5 961448649 14 279130562 530835402
0 505705299 11 487588093 488005936
5 956469930 6 776825480 857914491
5 173584499 5 68071790 127760171
5 617390756 2 289616458 604023215
2 281642201 14 245587163 273817065
5 411506287 9 42526705 317589066
3 547485462 9 271470684 437838096
5 996351074 6 74856...

output:

result:

ok 1000000 lines

Test #20:

score: 0

Accepted

time: 116ms

memory: 3684kb

input:

999999
0 105393047 8 55828222 95820891
2 914227808 13 365760112 463062746
3 447528560 10 304903588 410888549
1 573411702 5 477139815 538078040
5 443239658 13 283340857 321622039
5 729628729 7 260647549 560838179
3 215299701 10 34885046 213523791
2 859374122 1 544508624 795986441
4 864873312 7 416831...

output:

39992669
-1
-1
1
-1
-1
-1
1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
1
10573113
-1
1
-1
-1
1
1
-1
-1
-1
68522961
-1
-1
-1
1
-1
-1
1
1
-1
-1
-1
1
17590651
-1
-1
-1
-1
11554641
-1
1
1
1
-1
-1
288548258
447374910
-1
1
1
19114954
-1
-1
1
1
-1
-1
-1
1
-1
121545976
1
-1
-1
-1
-1
1
-1
-1
-1
22273383
-1
99473454...

result:

ok 999999 lines

Test #21:

score: 0

Accepted

time: 120ms

memory: 3664kb

input:

999998
4 95615249 9 44706863 82597067
1 296948618 14 221497167 253219866
4 407423323 14 395311431 402237613
4 562586582 7 215866474 332581531
5 461110170 3 8270545 13567149
1 601749155 15 70976179 302958983
2 932067490 13 282852789 866650449
3 392745208 11 84796685 215041796
5 181898334 11 141866145...

output:

result:

ok 999998 lines

Test #22:

score: 0

Accepted

time: 124ms

memory: 3508kb

input:

999997
0 790870149 10 312341665 750583643
4 384702127 1 220708338 372080663
2 662285387 10 14637938 407944387
0 473613609 3 314642869 447537089
4 773947983 9 367385950 465660605
5 473869581 14 442534885 461613235
0 726983133 1 417689049 679009425
5 221083595 5 123544654 169809378
0 872038508 7 57750...

output:

result:

ok 999997 lines

Test #23:

score: 0

Accepted

time: 117ms

memory: 3552kb

input:

999996
0 76059652 6 27025196 72899785
4 140538090 3 140356967 140371077
0 622180150 1 386081350 473991190
3 167821189 5 37470414 135098524
3 8637942 15 984215 5958852
1 51022707 6 15376414 50059575
0 443750923 11 345920051 385212659
3 459487380 15 354903169 361806660
4 562178684 12 325063103 5252331...

output:

result:

ok 999996 lines

Test #24:

score: 0

Accepted

time: 43ms

memory: 3692kb

input:

output:

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

result:

ok 1000000 lines

Test #25:

score: 0

Accepted

time: 42ms

memory: 3636kb

input:

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

output:

1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
2
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
2
-1
1
-1
-1
1
-1
1
-1
1
-1
-1
2
-1
1
2
1
-1
1
3
-1
-1
-1
1
1
-1
2
-1
-1
-1
-1
2
-1
-1
2
2
-1
-1
-1
1
-1
-1
-1
-1
1
1
-1
-1
2
-1
-1
-1
-1
-1
-1
3
-1
1
-1
-1
-1
-1
-1
1
-1
-1
1
1
-1
1
1
-1
1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1...

result:

ok 999999 lines

Test #26:

score: 0

Accepted

time: 50ms

memory: 3648kb

input:

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

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
2
-1
-1
3
1
-1
1
2
1
-1
-1
-1
1
1
2
-1
-1
1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
3
-1
-1
1
-1
1
-1
-1
1
1
-1
2
2
1
1
2
-1
2
-1
-1
-1
1
-1
2
-1
-1
-1
1
-1
-1
-1
1
-1
-1
-1
-1
1
4
-1
-1
1
1
-1
2
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
1
...

result:

ok 999998 lines

Test #27:

score: 0

Accepted

time: 42ms

memory: 3568kb

input:

output:

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

result:

ok 999997 lines

Test #28:

score: 0

Accepted

time: 46ms

memory: 3512kb

input:

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

output:

1
-1
6
-1
-1
1
8
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
2
1
1
1
-1
2
-1
-1
-1
-1
-1
-1
1
-1
2
1
1
-1
1
2
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
1
-1
2
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
4
1
2
1
-1
1
2
2
-1
-1
-1
1
-1
-1
2
1
1
-1
1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
1
-1
2
5
1
-1
-1
...

result:

ok 999996 lines

Extra Test:

score: 0

Extra Test Passed