#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t,sub_id,n,m,N,M;
int book[3005][3005];
int tot,sta[1000005][2];
void add(int x,int y){
	if (x==y||book[x][y]==1||book[y][x]==1)return;
	++tot;
	sta[tot][0]=x,sta[tot][1]=y;
	book[x][y]=book[y][x]=1;
	return;
}
void out(){
	printf("%d %d\n",N,tot);
	for (int i=1;i<=tot;i++)printf("%d %d\n",sta[i][0],sta[i][1]);
	return;
}
bool prime(int x){
	if (x<2)return 0;
	for (int i=2;i*i<=x;i++)
		if (x%i==0)return 0;
	return 1;
}
int main(){
	scanf("%d%d",&t,&sub_id);
	while(t--){
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
		}
		scanf("%d%d",&N,&M);
		tot=0;
		memset(book,0,sizeof(book));
		if (sub_id==1){
			for (int i=1;i<=N/2;i++)
				for (int j=N/2+1;j<=N;j++)
					add(i,j);
			out();
		}
		if (sub_id==2){
			for (int i=1;i<=N;i++)
				for (int j=i+1;j<=N;j++)
					if (i%(n-1)!=j%(n-1))add(i,j);
			out();
		}
		if (sub_id==3||sub_id==4||sub_id==5){
			int p=-1;
			for (int i=N;i>=1;i--)
				if (i*i<=N/2&&prime(i)){
					p=i;
					break;
				}
			int id=p*p;
			for (int i=0;i<p;i++)
				for (int d=0;d<p;d++){
					int s=++id;
					for (int j=0,t=i;j<p;j++,t=(t+d)%p)
						add(s,j*p+t+1);
				}
			out();
		}
	}
	return 0;
}