#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
#include <algorithm>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
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;
}
pair<int,int> e[1000005];
bitset<350> qwq[350];
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();
		}
		if (sub_id==6){
			for (int i=1;i<=N;i++)qwq[i].reset();
			int e_tot=0;
			for (int i=1;i<=N;i++)
				for (int j=i+1;j<=N;j++)
					e[++e_tot]=make_pair(i,j);
			shuffle(e+1,e+1+e_tot,rnd);
			for (int i=1;i<=e_tot;i++){
				int x=e[i].first,y=e[i].second;
				qwq[x][y]=qwq[y][x]=1;
				int fg=1;
				for (int k=1;k<=N&&fg==1;k++){
					if (k!=x&&(qwq[k]&qwq[x]).count()>3)fg=0;
					if (k!=y&&(qwq[k]&qwq[y]).count()>3)fg=0;
				}
				if (fg==1)add(x,y);
				else qwq[x][y]=qwq[y][x]=0;
			}
			out();
		}
	}
	return 0;
}