民间数据都过了，这次官方数据异常强。对拍几万组了没错误。

#include<bits/stdc++.h>
using namespace std;
inline int qr() {
	int k=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){k=(k<<1)+(k<<3)+(ch^48);ch=getchar();}
	return k;
}
const int M=2e6+2;
int n,m,k;
int a[M];
int ans[M*2];
int X[M*2],Y[M*2];
int to[602],up[602];
int cnt,tot,sp;
int zhan[302][10];
queue<int>q1;
queue<int>q2;
int Nx,AC,AC100,geiwoA;
int main() {
//	freopen("meow.in","r",stdin);
	for(int T=qr();T;T--) {
		n=qr(),m=qr(),k=qr();
		for(int i=1;i<=m;i++) a[i]=qr();
		while(q1.size()) q1.pop();
		while(q2.size()) q2.pop();
		for(int i=1;i<n;i++)
			q1.push(i),q2.push(i);
		tot=cnt=0;sp=n;AC=Nx=0;
		for(int i=1;i<=m;i++) {
			int x=a[i];
			if(AC&&x==AC100&&to[x]==0) {
				ans[++tot]=1;
				X[tot]=geiwoA;
				to[x]=geiwoA;
				up[x]=3;
				zhan[to[x]][3]=x;
				continue;
			}
			if(x==AC) {
//				printf("!%d\n",i);
				ans[++tot]=1;
				X[tot]=sp;
//				to[x]=sp;
//				up[x]=2;
//				zhan[to[x]][2]=x;
				continue;
			}
			if(to[x]) {
//				printf("%d %d %d %d\n",i,to[x],up[x],zhan[to[x]][2]);
				if(up[x]==1) {
					if(to[x]==sp&&Nx) q2.push(Nx),Nx=0,AC=0;
					if(!zhan[to[x]][2]) {
						ans[++tot]=1;
						X[tot]=to[x];
						if(to[x]!=sp) q1.push(to[x]);
						zhan[to[x]][1]=0;
					}
					else {
						ans[++tot]=1;
						X[tot]=sp;
						ans[++tot]=2;
						X[tot]=sp;
						Y[tot]=to[x];
						if(to[x]==to[AC]) AC=AC100=0;
						zhan[to[x]][1]=zhan[to[x]][2];
						zhan[to[x]][2]=zhan[to[x]][3];
						zhan[to[x]][3]=0;
						if(zhan[to[x]][1]) up[zhan[to[x]][1]]=1;
						if(zhan[to[x]][2]) up[zhan[to[x]][2]]=2;
						if(zhan[to[x]][1]&&(!zhan[to[x]][2])&&to[x]!=sp) q2.push(to[x]);
						if((!zhan[to[x]][1])&&to[x]!=sp) q1.push(to[x]);
					}
					to[x]=up[x]=0;
				}
				else {
					if((up[x]==2&&zhan[to[x]][3])||zhan[sp][1]==x) {
						ans[++tot]=1;
						X[tot]=sp;
						if(zhan[sp][1]==x) zhan[sp][1]=0;
						else zhan[sp][1]=x;
					}
					//
					else {
						ans[++tot]=1;
						X[tot]=to[x];
						if(up[x]==2&&to[x]!=sp) q2.push(to[x]);
						zhan[to[x]][up[x]]=0;to[x]=up[x]=0;
					}
				}
				//--cnt;
			}
			else {
				if((!q1.size())&&(!q2.size())) {
					int nx;
					for(int j=i+1;j<=m;j++) {
						if(up[a[j]]==1) {
							nx=j;break;
						}
					}
					int vis=0;
					for(int j=i+1;j<nx;j++) {
						if(to[a[j]]==to[a[nx]]) ++vis;
					}
//					printf("%d %d %d %d????\n",vis,nx,to[a[nx]],up[a[nx-1]]);
					if(vis&1) {
						ans[++tot]=1;
						X[tot]=sp;
//						++cnt;
						to[x]=sp;
						up[x]=1;
						Nx=sp;
						zhan[sp][1]=x;
						sp=to[a[nx]];
						AC=zhan[sp][2];
						to[AC]=up[AC]=0;
						zhan[sp][2]=0;
//						printf("##%d %d %d\n",sp,AC,YES);
					}
					else {
						ans[++tot]=1;
						X[tot]=to[a[nx]];
//						++cnt;
						to[x]=to[a[nx]];
						up[x]=3;
						zhan[to[x]][3]=x;
						AC=zhan[to[x]][2];
						geiwoA=to[x];
						AC100=x;
					}
				}
				else {
					if(q1.size()) {
						to[x]=q1.front();
						q1.pop();
						up[x]=1;
						zhan[to[x]][1]=x;
					}
					else {
						to[x]=q2.front();
						q2.pop();
						up[x]=2;
						zhan[to[x]][2]=x;
					}
					ans[++tot]=1;
					X[tot]=to[x];
//					printf("#%d %d %d\n",i,x,to[x]);
//					++cnt;
				}
			}
		}
		printf("%d\n",tot);
		for(int i=1;i<=tot;i++) {
			printf("%d ",ans[i]);
			if(ans[i]==1) printf("%d\n",X[i]);
			else printf("%d %d\n",X[i],Y[i]);
		}
	}
	return 0;
}