QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143148#6502. Disjoint Set UnionqzezTL 184ms11528kbC++142.4kb2023-08-20 18:26:552023-08-20 18:26:57

Judging History

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

  • [2023-08-20 18:26:57]
  • 评测
  • 测评结果:TL
  • 用时:184ms
  • 内存:11528kb
  • [2023-08-20 18:26:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e3+10;
int T,n,fa[N],a[N],col[N],p[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int Find(int x){
	return fa[x]==x?x:Find(fa[x]);
}
vector<tuple<int,int,int> >ans;
void merge(int x,int y){
	ans.push_back({2,x,y});
	x=find(x),y=find(y);
	if(x^y)fa[x]=y;
}
int k,in[N],id[N];
vector<int>to[N];
bool topo(){
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(!in[i])q.push(i);
	}
	k=0;
	for(int u;!q.empty();){
		id[++k]=u=q.front(),q.pop();
		for(int v:to[u]){
			if(!--in[v])q.push(v);
		}
	}
	return k==n;
}
void add(int u,int v){
	if(u==v)return;
	// debug(u,v);
	to[u].push_back(v),in[v]++;
}
bool get(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&fa[i]);
		if(fa[i]^i)add(fa[i],i);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]^i)add(Find(a[i]),Find(i));
	}
	// if(T==1e5-136){
	// 	cout<<n<<endl<<ary(fa,1,n)<<endl<<ary(a,1,n)<<endl;
	// 	exit(0);
	// }
	if(!topo())return 0;
	// debug("OK1");
	for(int i=1;i<=n;i++){
		for(col[i]=i;a[col[i]]^col[i];col[i]=a[col[i]]);
	}
	// for(int i=1;i<=n;i++)debug(ary(anc[i],1,n));
	// debug(ary(id,1,n));
	// debug(ary(col,1,n));
	for(int i=n,u;u=id[i],i>=1;i--){
		if(fa[u]==u)
			for(int j=i+1,v;v=id[j],j<=n;j++){
				if(col[u]==col[v]&&fa[v]==v)merge(v,u);
			}
		for(int v=1;v<=n;v++){
			if(fa[v]!=a[v]&&fa[v]!=v&&fa[v]!=u&&fa[fa[v]]==u){
				merge(v,u);
			}
		}
		// debug(u,ary(fa,1,n));
	}
	// debug("OK2");
	for(int i=1;i<=n;i++)if(fa[i]^a[i])return 0;
	// if(T>10)return 1;
	puts("YES");
	printf("%d\n",(int)ans.size());
	for(auto x:ans){
		if(get<0>(x)==1)printf("%d %d\n",get<0>(x),get<1>(x));
		else printf("%d %d %d\n",get<0>(x),get<1>(x),get<2>(x));
	}
	return 1;
}
void clr(){
	ans.clear();
	for(int i=1;i<=n;i++)to[i].clear(),in[i]=0;
	// for(int i=1;i<=n;i++)fill(anc[i]+1,anc[i]+1+n,0);
}
int main(){
	for(scanf("%d",&T);T--;clr())if(!get())puts("NO");
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3744kb

input:

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

output:

YES
1
2 1 2
YES
4
2 3 2
2 4 2
2 2 1
2 3 1
YES
4
2 1 2
2 2 3
2 3 4
2 4 5
NO
YES
7
2 6 2
2 2 5
2 3 5
2 5 4
2 2 4
2 4 1
2 2 1

result:

ok good! (YES count = 4, NO count = 1) (5 test cases)

Test #2:

score: 0
Accepted
time: 138ms
memory: 3816kb

input:

100000
5
1 2 1 1 1
2 2 1 1 2
5
3 2 3 4 1
3 2 3 4 1
5
1 2 3 4 3
1 4 4 1 1
5
1 2 3 5 3
1 2 2 5 2
5
5 2 3 5 5
5 2 3 5 5
5
1 2 3 4 5
5 3 3 4 5
5
1 2 3 4 5
1 4 1 4 4
5
1 2 3 1 5
1 2 3 1 2
5
1 2 3 3 1
1 3 3 3 1
5
1 2 3 4 3
2 2 4 4 4
5
1 2 2 4 5
5 2 2 4 5
5
1 2 1 4 5
5 2 5 5 5
5
1 2 3 4 5
1 2 5 5 1
5
1 4 3...

output:

YES
2
2 1 2
2 5 2
YES
0
YES
7
2 3 2
2 5 2
2 2 4
2 3 4
2 5 4
2 4 1
2 5 1
YES
2
2 3 2
2 5 2
YES
0
YES
2
2 1 5
2 2 3
YES
4
2 5 2
2 2 4
2 5 4
2 3 1
YES
1
2 5 2
YES
1
2 2 3
YES
3
2 3 4
2 5 4
2 1 2
YES
1
2 1 5
YES
4
2 4 1
2 1 5
2 3 5
2 4 5
YES
4
2 4 3
2 3 5
2 4 5
2 5 1
YES
5
2 4 3
2 2 3
2 3 1
2 2 1
2 5 1
...

result:

ok good! (YES count = 100000, NO count = 0) (100000 test cases)

Test #3:

score: 0
Accepted
time: 174ms
memory: 3804kb

input:

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

output:

YES
1
2 2 10
YES
21
2 5 2
2 8 2
2 9 2
2 2 4
2 5 4
2 7 4
2 8 4
2 9 4
2 4 3
2 2 3
2 5 3
2 7 3
2 8 3
2 9 3
2 3 6
2 2 6
2 4 6
2 5 6
2 7 6
2 8 6
2 9 6
YES
20
2 10 2
2 8 2
2 2 7
2 8 7
2 10 7
2 7 4
2 5 4
2 6 4
2 8 4
2 4 1
2 5 1
2 6 1
2 7 1
2 8 1
2 1 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
YES
23
2 5 7
2 10 3
2 3 8...

result:

ok good! (YES count = 50000, NO count = 0) (50000 test cases)

Test #4:

score: 0
Accepted
time: 95ms
memory: 3756kb

input:

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

output:

YES
37
2 9 8
2 1 8
2 12 8
2 8 19
2 9 19
2 19 18
2 8 18
2 9 18
2 16 18
2 18 17
2 16 17
2 19 17
2 17 14
2 16 14
2 18 14
2 19 14
2 14 5
2 16 5
2 17 5
2 18 5
2 19 5
2 5 13
2 14 13
2 16 13
2 17 13
2 18 13
2 19 13
2 13 4
2 5 4
2 14 4
2 16 4
2 17 4
2 18 4
2 19 4
2 4 6
2 13 6
2 11 3
YES
58
2 20 19
2 16 19
2...

result:

ok good! (YES count = 12500, NO count = 0) (12500 test cases)

Test #5:

score: 0
Accepted
time: 94ms
memory: 3756kb

input:

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

output:

YES
102
2 19 5
2 5 17
2 9 17
2 15 17
2 18 17
2 19 17
2 17 7
2 5 7
2 9 7
2 15 7
2 18 7
2 19 7
2 7 20
2 5 20
2 8 20
2 9 20
2 15 20
2 17 20
2 18 20
2 19 20
2 20 16
2 5 16
2 7 16
2 8 16
2 9 16
2 15 16
2 17 16
2 18 16
2 19 16
2 16 14
2 5 14
2 7 14
2 8 14
2 9 14
2 15 14
2 17 14
2 18 14
2 19 14
2 20 14
2 1...

result:

ok good! (YES count = 12500, NO count = 0) (12500 test cases)

Test #6:

score: 0
Accepted
time: 94ms
memory: 3892kb

input:

500
100
5 43 3 13 100 6 56 8 9 62 11 82 13 14 15 48 17 76 19 64 35 62 50 77 38 94 35 62 35 30 31 32 48 34 35 36 43 64 39 40 35 42 62 44 45 62 47 62 49 50 62 47 62 62 39 48 20 58 59 60 43 66 19 62 3 66 67 85 69 70 83 28 73 83 100 76 77 80 85 80 81 82 100 84 85 40 20 88 62 90 40 92 93 94 58 96 30 98 6...

output:

YES
2679
2 25 64
2 57 64
2 7 48
2 1 100
2 71 100
2 2 62
2 72 62
2 11 77
2 77 58
2 11 58
2 24 58
2 58 94
2 11 94
2 24 94
2 74 94
2 75 94
2 77 94
2 95 94
2 94 66
2 1 66
2 5 66
2 10 66
2 11 66
2 16 66
2 22 66
2 24 66
2 26 66
2 33 66
2 37 66
2 46 66
2 51 66
2 53 66
2 54 66
2 58 66
2 61 66
2 71 66
2 74 6...

result:

ok good! (YES count = 500, NO count = 0) (500 test cases)

Test #7:

score: 0
Accepted
time: 96ms
memory: 4404kb

input:

55
300
172 231 135 149 135 297 7 297 236 52 73 114 52 135 15 73 297 97 218 236 52 236 218 73 244 236 73 52 162 218 103 30 214 34 59 36 73 89 44 131 73 73 73 73 73 41 47 32 236 52 248 73 73 54 209 75 57 73 205 151 73 62 73 73 143 141 238 205 106 73 71 128 73 124 75 76 89 231 205 73 149 135 249 135 13...

output:

YES
6960
2 171 108
2 48 30
2 252 176
2 69 59
2 242 145
2 51 250
2 1 236
2 33 218
2 111 205
2 165 157
2 12 135
2 55 135
2 122 135
2 126 135
2 146 135
2 170 135
2 188 135
2 268 135
2 204 131
2 94 52
2 158 52
2 233 52
2 29 44
2 259 44
2 276 44
2 2 73
2 3 73
2 4 73
2 5 73
2 6 73
2 8 73
2 9 73
2 13 73
2 ...

result:

ok good! (YES count = 55, NO count = 0) (55 test cases)

Test #8:

score: 0
Accepted
time: 84ms
memory: 10968kb

input:

5
1000
794 193 3 4 888 279 316 8 621 679 376 254 791 550 362 706 677 133 133 279 279 57 557 471 780 471 110 557 264 317 557 927 264 908 589 193 481 38 39 941 619 473 683 340 817 780 876 548 557 193 589 648 264 471 940 528 557 710 57 57 61 142 133 481 679 142 712 264 557 264 683 468 679 204 398 754 3...

output:

YES
25148
2 991 961
2 82 66
2 230 66
2 201 317
2 942 712
2 285 548
2 545 548
2 756 548
2 498 180
2 109 37
2 633 105
2 190 940
2 205 940
2 675 940
2 7 908
2 79 908
2 181 648
2 692 550
2 702 550
2 41 528
2 42 142
2 291 887
2 252 876
2 9 817
2 269 797
2 449 797
2 659 794
2 32 791
2 157 791
2 792 791
2 ...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #9:

score: 0
Accepted
time: 47ms
memory: 11320kb

input:

5
1000
811 448 371 731 601 6 950 8 731 811 123 688 753 282 15 802 17 282 282 20 272 818 23 24 731 1 805 67 951 753 230 182 629 15 874 36 576 38 113 272 41 811 43 455 282 595 965 836 582 855 811 76 230 50 731 885 811 595 182 969 619 62 688 576 811 944 335 1 944 230 71 42 73 328 11 951 753 10 335 944 ...

output:

YES
110830
2 430 564
2 375 944
2 496 944
2 845 944
2 893 944
2 686 636
2 571 210
2 778 210
2 343 76
2 28 335
2 165 335
2 278 335
2 331 335
2 609 335
2 712 335
2 777 335
2 860 335
2 33 230
2 274 230
2 346 230
2 356 230
2 729 230
2 549 50
2 730 50
2 485 438
2 27 316
2 865 316
2 755 965
2 2 895
2 237 6...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #10:

score: 0
Accepted
time: 102ms
memory: 10192kb

input:

5
1000
1 696 3 4 70 98 715 8 174 10 11 12 342 530 15 878 928 191 447 20 21 878 23 436 367 4 174 28 321 666 31 911 33 34 35 526 66 38 39 868 41 440 43 710 45 988 47 48 62 50 383 612 300 569 878 56 84 58 560 60 61 401 63 64 815 647 67 68 69 70 670 72 73 74 75 846 77 784 554 80 208 82 142 84 85 590 87 ...

output:

YES
352389
2 18 395
2 133 37
2 32 856
2 124 707
2 224 564
2 597 564
2 242 428
2 761 428
2 44 53
2 990 53
2 462 793
2 255 384
2 896 384
2 981 384
2 460 66
2 941 878
2 185 445
2 921 269
2 204 391
2 417 783
2 51 433
2 544 142
2 871 666
2 338 554
2 558 319
2 333 390
2 100 42
2 1000 999
2 999 998
2 250 9...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #11:

score: 0
Accepted
time: 140ms
memory: 11124kb

input:

5
1000
1 697 3 807 656 548 7 859 9 188 11 194 629 907 319 275 796 18 876 878 21 711 376 82 275 118 27 28 144 30 31 32 878 225 35 795 193 835 39 220 468 509 601 808 569 46 947 871 859 878 228 52 113 697 621 56 319 616 323 572 970 795 98 994 65 853 907 387 69 436 605 835 601 74 762 256 77 78 275 907 5...

output:

YES
258420
2 143 542
2 766 739
2 555 915
2 370 778
2 279 51
2 983 695
2 373 789
2 891 256
2 91 853
2 526 853
2 411 795
2 604 795
2 268 697
2 749 697
2 26 629
2 37 629
2 209 629
2 338 333
2 543 333
2 948 333
2 106 228
2 571 228
2 597 137
2 214 113
2 551 113
2 637 113
2 727 113
2 414 67
2 677 937
2 26...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #12:

score: 0
Accepted
time: 96ms
memory: 10556kb

input:

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

output:

YES
471176
2 158 664
2 664 213
2 158 213
2 213 51
2 158 51
2 664 51
2 51 426
2 158 426
2 213 426
2 664 426
2 426 845
2 51 845
2 158 845
2 213 845
2 322 845
2 664 845
2 845 871
2 51 871
2 158 871
2 213 871
2 322 871
2 426 871
2 664 871
2 871 720
2 51 720
2 158 720
2 213 720
2 322 720
2 426 720
2 664 ...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #13:

score: 0
Accepted
time: 132ms
memory: 10584kb

input:

5
1000
1 2 3 4 5 6 7 69 9 10 11 12 13 14 15 16 17 18 822 423 21 22 23 24 25 26 27 28 29 30 848 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 963 48 49 50 51 52 53 54 672 56 673 58 59 60 868 62 63 64 480 66 67 68 69 941 71 834 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 515 91 92 93 94 95 96 97...

output:

YES
378848
2 474 942
2 932 508
2 508 315
2 932 315
2 315 241
2 508 241
2 932 241
2 196 230
2 241 155
2 315 155
2 508 155
2 932 155
2 155 723
2 241 723
2 315 723
2 508 723
2 932 723
2 723 766
2 155 766
2 241 766
2 315 766
2 508 766
2 932 766
2 766 762
2 155 762
2 241 762
2 315 762
2 508 762
2 723 762...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #14:

score: 0
Accepted
time: 103ms
memory: 11376kb

input:

5
1000
433 256 696 228 253 435 436 725 47 766 308 958 433 851 399 433 258 328 748 435 468 725 982 24 748 157 748 999 958 725 27 553 435 819 139 553 748 304 39 676 289 228 33 725 748 851 811 735 435 47 819 399 531 435 738 191 433 304 559 60 748 800 227 47 982 658 47 586 69 748 991 191 325 107 183 644...

output:

YES
61660
2 430 328
2 494 289
2 942 289
2 17 178
2 371 346
2 761 110
2 706 256
2 115 879
2 231 213
2 503 401
2 324 767
2 5 725
2 32 725
2 75 725
2 198 725
2 266 725
2 287 725
2 311 725
2 613 725
2 808 725
2 818 725
2 846 725
2 21 399
2 594 399
2 917 399
2 295 227
2 187 191
2 176 906
2 387 906
2 544 ...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #15:

score: 0
Accepted
time: 184ms
memory: 10920kb

input:

5
1000
766 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 592 18 19 20 21 22 230 24 25 26 27 28 29 30 31 32 270 144 35 36 37 105 39 40 180 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 947 61 62 417 64 65 66 67 68 69 70 71 72 73 888 75 76 77 78 79 80 81 82 83 766 85 86 87 214 916 90 91 92 93 94 95 317...

output:

YES
452366
2 774 916
2 3 1000
2 368 1000
2 1000 999
2 3 999
2 368 999
2 999 998
2 3 998
2 368 998
2 1000 998
2 998 997
2 3 997
2 368 997
2 999 997
2 1000 997
2 997 481
2 3 481
2 368 481
2 996 481
2 998 481
2 999 481
2 1000 481
2 481 995
2 3 995
2 247 995
2 368 995
2 996 995
2 997 995
2 998 995
2 999...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #16:

score: 0
Accepted
time: 128ms
memory: 11096kb

input:

5
1000
392 897 227 735 327 707 615 226 153 102 593 398 726 696 857 894 17 823 799 322 109 714 931 260 762 823 988 827 799 949 694 916 867 123 398 747 633 367 931 916 231 89 891 44 45 538 938 175 49 376 799 762 960 696 327 327 997 477 726 799 857 714 339 398 916 231 799 68 69 894 71 696 73 255 50 395...

output:

YES
154296
2 573 950
2 219 818
2 473 818
2 135 417
2 75 376
2 6 89
2 33 89
2 36 89
2 106 89
2 271 89
2 283 89
2 684 949
2 833 412
2 215 281
2 10 868
2 447 762
2 675 762
2 809 762
2 506 609
2 666 609
2 784 609
2 290 463
2 517 463
2 699 463
2 155 327
2 338 327
2 380 87
2 906 743
2 2 408
2 307 408
2 48...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #17:

score: 0
Accepted
time: 62ms
memory: 6476kb

input:

5
1000
1 702 632 4 5 629 7 8 9 10 713 371 13 14 15 16 17 785 19 20 21 476 23 24 584 26 54 28 29 30 31 32 33 34 35 36 768 239 39 96 809 42 43 44 45 46 47 48 208 50 51 52 53 937 55 56 57 58 59 606 25 62 255 64 65 435 67 68 69 70 70 72 69 564 75 76 615 78 79 255 564 800 537 84 85 86 564 262 89 90 91 92...

output:

YES
214718
2 265 973
2 359 907
2 99 476
2 715 975
2 803 517
2 329 834
2 650 834
2 256 753
2 544 358
2 982 322
2 753 728
2 256 728
2 712 728
2 727 728
2 728 117
2 175 117
2 256 117
2 656 117
2 672 117
2 712 117
2 727 117
2 753 117
2 850 117
2 117 790
2 175 790
2 256 790
2 656 790
2 672 790
2 712 790
...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #18:

score: 0
Accepted
time: 81ms
memory: 11528kb

input:

5
1000
167 610 3 858 1 592 201 496 9 10 11 969 13 14 290 705 618 18 19 62 21 22 23 25 25 562 509 28 29 162 31 32 1 502 518 1 906 501 39 40 41 42 43 44 779 17 979 530 49 737 51 52 53 54 55 56 57 779 533 60 61 822 54 64 65 66 509 68 69 562 71 72 73 587 509 76 77 78 848 80 81 723 83 84 142 936 562 868 ...

output:

YES
278143
2 174 710
2 38 811
2 109 530
2 411 530
2 448 530
2 2 1
2 253 1
2 156 562
2 460 562
2 683 562
2 148 778
2 4 509
2 674 509
2 689 509
2 835 509
2 925 248
2 328 500
2 454 944
2 20 822
2 187 822
2 450 515
2 336 966
2 820 171
2 205 779
2 233 779
2 498 331
2 864 915
2 5 915
2 26 915
2 27 915
2 3...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #19:

score: 0
Accepted
time: 103ms
memory: 10592kb

input:

5
1000
404 627 3 4 5 6 7 8 9 10 11 12 13 14 693 16 17 18 19 20 221 22 23 24 25 26 27 28 29 30 31 32 33 718 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 986 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 503 551 994 89 495 91 447 93 94 495 96 ...

output:

YES
205010
2 529 716
2 716 220
2 529 220
2 220 639
2 529 639
2 716 639
2 639 863
2 220 863
2 529 863
2 716 863
2 863 827
2 220 827
2 529 827
2 639 827
2 716 827
2 827 780
2 220 780
2 529 780
2 639 780
2 716 780
2 863 780
2 780 500
2 220 500
2 529 500
2 639 500
2 716 500
2 827 500
2 863 500
2 500 627...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #20:

score: 0
Accepted
time: 159ms
memory: 10068kb

input:

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

output:

YES
106015
2 399 486
2 486 455
2 399 455
2 455 184
2 399 184
2 486 184
2 184 796
2 399 796
2 455 796
2 486 796
2 796 681
2 184 681
2 399 681
2 455 681
2 486 681
2 681 846
2 184 846
2 399 846
2 455 846
2 486 846
2 796 846
2 846 104
2 184 104
2 399 104
2 455 104
2 486 104
2 681 104
2 796 104
2 104 805...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #21:

score: 0
Accepted
time: 117ms
memory: 3688kb

input:

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

output:

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

result:

ok good! (YES count = 50000, NO count = 0) (50000 test cases)

Test #22:

score: 0
Accepted
time: 62ms
memory: 3832kb

input:

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

output:

YES
1
2 7 3
YES
9
2 9 1
2 14 13
2 13 12
2 14 12
2 18 15
2 6 8
2 1 7
2 12 3
2 13 3
YES
11
2 17 10
2 8 10
2 10 7
2 3 7
2 17 7
2 2 14
2 7 6
2 3 6
2 10 6
2 17 6
2 9 4
YES
33
2 14 7
2 2 7
2 7 4
2 2 4
2 14 4
2 18 4
2 4 8
2 2 8
2 7 8
2 13 8
2 18 8
2 8 5
2 2 5
2 4 5
2 13 5
2 5 3
2 2 3
2 4 3
2 8 3
2 13 3
2 3...

result:

ok good! (YES count = 12500, NO count = 0) (12500 test cases)

Test #23:

score: 0
Accepted
time: 20ms
memory: 3908kb

input:

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

output:

YES
103
2 100 68
2 68 41
2 100 41
2 41 13
2 68 13
2 100 13
2 93 70
2 13 18
2 41 18
2 68 18
2 100 18
2 70 31
2 93 31
2 31 76
2 70 76
2 93 76
2 43 12
2 32 30
2 30 1
2 32 1
2 46 42
2 96 39
2 39 26
2 96 26
2 18 81
2 76 92
2 31 92
2 92 89
2 31 89
2 76 89
2 89 66
2 31 66
2 76 66
2 92 66
2 66 53
2 31 53
2 ...

result:

ok good! (YES count = 500, NO count = 0) (500 test cases)

Test #24:

score: 0
Accepted
time: 23ms
memory: 4000kb

input:

55
300
73 84 3 257 5 257 111 8 265 10 74 73 279 81 277 73 17 73 19 227 124 174 23 93 25 81 81 257 29 208 31 32 37 175 74 265 37 257 125 40 176 42 171 132 277 124 248 48 49 187 51 52 53 147 55 132 277 53 124 60 194 81 277 271 65 66 44 171 211 45 277 72 73 257 257 76 79 299 133 277 73 257 132 81 271 1...

output:

YES
4607
2 117 93
2 278 79
2 236 146
2 220 74
2 262 165
2 78 129
2 177 277
2 148 257
2 196 257
2 67 132
2 264 132
2 288 124
2 20 81
2 88 81
2 4 73
2 35 73
2 38 73
2 56 73
2 57 73
2 59 73
2 63 73
2 71 73
2 83 73
2 87 73
2 90 73
2 91 73
2 99 73
2 110 73
2 114 73
2 115 73
2 116 73
2 121 73
2 122 73
2 1...

result:

ok good! (YES count = 55, NO count = 0) (55 test cases)

Test #25:

score: 0
Accepted
time: 6ms
memory: 3776kb

input:

5
1000
1 2 3 4 705 6 7 8 9 10 11 781 13 231 15 16 17 18 19 20 21 22 23 24 25 26 27 401 29 42 31 445 667 289 35 36 37 761 996 40 41 42 43 251 45 46 47 231 49 50 51 52 53 54 55 56 57 35 59 60 61 62 63 64 65 66 538 401 69 70 71 72 73 74 75 554 77 78 79 344 81 82 83 84 85 442 51 88 89 90 91 92 93 94 891...

output:

YES
9
2 157 924
2 400 845
2 812 795
2 942 501
2 913 318
2 240 318
2 480 183
2 189 77
2 886 45
YES
46
2 555 150
2 858 309
2 314 995
2 133 984
2 884 967
2 412 961
2 925 936
2 38 931
2 866 917
2 675 906
2 398 880
2 417 835
2 661 819
2 152 817
2 256 777
2 571 697
2 211 693
2 150 686
2 983 682
2 114 669
...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #26:

score: 0
Accepted
time: 7ms
memory: 3832kb

input:

5
1000
736 2 3 4 5 6 7 8 9 10 11 797 823 929 15 16 17 18 19 20 264 22 23 24 52 353 27 28 29 30 839 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 944 51 52 403 872 55 56 57 58 59 60 61 62 63 64 99 66 67 68 69 70 71 72 73 938 302 186 77 78 79 80 81 82 83 84 85 86 983 86 89 90 91 46 93 94 95 96...

output:

YES
110
2 993 549
2 1 778
2 995 981
2 909 566
2 74 391
2 721 162
2 903 162
2 219 9
2 400 346
2 551 8
2 997 843
2 394 375
2 375 135
2 394 135
2 86 848
2 724 325
2 130 752
2 549 924
2 577 23
2 94 1000
2 184 998
2 118 991
2 155 962
2 655 953
2 778 948
2 327 943
2 636 937
2 964 933
2 767 917
2 766 912
2...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #27:

score: 0
Accepted
time: 11ms
memory: 4412kb

input:

5
1000
487 446 3 4 5 6 442 8 452 10 601 12 300 895 15 208 866 328 19 20 21 967 644 24 25 118 27 28 787 30 31 344 33 139 350 440 37 369 39 918 41 42 190 483 45 46 556 48 360 807 188 608 53 67 55 333 398 397 853 60 61 953 676 678 65 66 882 483 69 369 71 72 763 576 75 76 77 78 724 574 310 193 83 84 85 ...

output:

YES
249
2 482 939
2 68 328
2 213 882
2 888 393
2 781 393
2 940 393
2 393 832
2 210 832
2 423 832
2 482 832
2 781 832
2 867 832
2 888 832
2 939 832
2 940 832
2 832 326
2 210 326
2 393 326
2 423 326
2 482 326
2 781 326
2 939 326
2 940 326
2 326 240
2 210 240
2 393 240
2 423 240
2 482 240
2 781 240
2 8...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #28:

score: 0
Accepted
time: 6ms
memory: 3860kb

input:

5
1000
588 923 119 77 5 6 7 8 9 10 11 12 13 477 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 987 155 153 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 369 53 54 764 56 341 305 932 430 61 663 63 462 65 66 67 68 69 70 884 72 73 74 180 76 77 78 609 80 81 82 83 739 85 86 87 400 183 90 91 92 6...

output:

YES
52
2 376 546
2 546 250
2 376 250
2 134 460
2 679 856
2 571 856
2 540 153
2 667 410
2 345 941
2 911 931
2 435 925
2 622 918
2 723 858
2 141 837
2 250 770
2 546 770
2 869 737
2 460 735
2 235 722
2 662 717
2 170 707
2 226 698
2 248 683
2 969 660
2 181 648
2 288 626
2 211 619
2 400 583
2 11 562
2 93...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #29:

score: 0
Accepted
time: 9ms
memory: 3916kb

input:

5
1000
816 2 519 284 253 990 965 581 457 414 232 451 581 519 581 406 581 965 581 20 519 337 383 253 581 26 27 587 900 34 862 215 915 439 439 370 816 189 387 134 103 249 361 964 809 367 47 103 452 760 67 862 253 915 467 103 215 439 816 516 581 103 87 581 439 66 249 68 621 497 71 417 581 439 63 673 10...

output:

YES
1024
2 609 370
2 531 337
2 851 826
2 1 821
2 725 821
2 173 253
2 513 101
2 269 87
2 449 58
2 4 581
2 161 581
2 258 581
2 271 581
2 310 581
2 328 581
2 830 581
2 18 439
2 38 439
2 272 439
2 293 439
2 372 439
2 384 439
2 464 439
2 575 439
2 693 439
2 903 439
2 967 439
2 751 311
2 37 311
2 40 311
2...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #30:

score: 0
Accepted
time: 2ms
memory: 3912kb

input:

5
1000
816 2 235 51 617 979 7 981 979 113 604 984 51 773 790 33 750 466 14 803 556 190 349 51 733 816 190 207 828 816 885 76 47 880 850 349 767 773 120 141 500 979 27 44 883 190 816 630 869 984 773 141 154 900 773 349 349 500 786 118 750 154 516 349 30 154 883 113 733 979 197 451 816 816 816 51 815 ...

output:

YES
3427
2 325 840
2 166 207
2 11 30
2 582 806
2 60 733
2 275 733
2 285 979
2 758 979
2 240 816
2 515 816
2 754 816
2 781 816
2 562 349
2 946 225
2 31 154
2 386 141
2 423 120
2 874 120
2 899 120
2 563 113
2 87 51
2 88 51
2 150 51
2 156 51
2 176 51
2 469 51
2 606 51
2 652 51
2 807 51
2 10 773
2 19 77...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #31:

score: 0
Accepted
time: 8ms
memory: 4016kb

input:

5
1000
1 2 3 22 949 6 7 8 9 10 11 12 547 33 1 16 17 520 19 20 21 22 23 928 111 26 631 994 29 236 657 32 33 34 35 898 37 38 765 685 41 42 43 44 45 46 961 48 49 556 51 619 53 785 55 56 57 180 59 60 61 62 166 64 65 66 67 95 69 70 71 72 73 74 75 866 77 78 79 80 328 82 257 243 85 86 87 88 89 90 91 92 93 ...

output:

YES
280
2 765 186
2 762 735
2 186 595
2 765 595
2 595 443
2 27 443
2 186 443
2 765 443
2 394 699
2 224 293
2 293 64
2 224 64
2 566 376
2 350 839
2 191 163
2 163 86
2 191 86
2 492 601
2 182 601
2 981 328
2 708 433
2 433 343
2 708 343
2 966 35
2 443 861
2 27 861
2 595 861
2 631 861
2 699 806
2 806 159...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #32:

score: 0
Accepted
time: 10ms
memory: 5116kb

input:

5
1000
1 2 924 4 5 6 7 8 9 10 867 919 13 8 15 850 17 18 922 20 884 543 23 824 25 47 990 28 29 30 791 32 33 34 35 208 37 38 39 491 41 870 43 274 45 46 47 410 49 50 871 52 53 54 55 540 57 58 59 60 61 62 63 94 65 66 67 68 924 70 71 72 73 74 75 76 407 78 79 980 81 82 83 84 85 86 87 514 89 90 91 92 619 9...

output:

YES
187
2 156 124
2 212 407
2 124 844
2 804 844
2 695 648
2 212 648
2 403 648
2 407 648
2 648 50
2 212 50
2 403 50
2 407 50
2 695 50
2 844 656
2 124 656
2 656 316
2 124 316
2 844 316
2 316 149
2 656 149
2 885 948
2 709 13
2 935 270
2 698 772
2 50 633
2 212 633
2 403 633
2 407 633
2 648 633
2 695 633...

result:

ok good! (YES count = 5, NO count = 0) (5 test cases)

Test #33:

score: -100
Time Limit Exceeded

input:

100000
4
1 2 3 1
3 1 1 4
4
1 2 3 4
4 1 4 2
4
1 2 3 4
1 1 3 3
4
1 2 1 4
4 3 4 1
4
1 2 3 4
2 3 2 4
4
1 3 3 3
2 3 1 4
4
1 2 3 4
2 3 4 4
4
1 2 2 2
2 3 1 4
4
1 2 3 4
2 4 1 1
4
2 3 3 4
3 1 3 3
4
1 2 3 4
3 3 4 2
4
3 1 3 1
3 2 4 2
4
1 2 1 1
3 4 4 1
4
1 2 4 4
3 1 2 3
4
2 2 3 4
3 3 2 3
4
1 2 3 3
1 4 4 4
4
2 2...

output:


result: