#include<bits/stdc++.h>
#define poly vector<int>
#define ull unsigned long long 
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
#define N 3005
using namespace std;
int id;
int n,m;
bitset<3005>f[3005];
int col[N];
poly G[3005];
mt19937_64 gen(time(0));
void BellaKira()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
	}
	if (id==1)
	{
		cin>>n>>m;
		cout<<n<<" "<<n/2*(n-n/2)<<'\n';
		for (int i=1;i<=n/2;i++)
			for (int j=n/2+1;j<=n;j++)
				cout<<i<<" "<<j<<'\n';
		return;
	}
	if (id==2)
	{
		int o,p;
		cin>>o>>p;
		int tot=0;
		n--;
		for (int i=1;i<=o;i++)
			for (int j=i+1;j<=o;j++)
				if (i%n!=j%n) tot++;
		cout<<o<<" "<<tot<<'\n';
		for (int i=1;i<=o;i++)
			for (int j=i+1;j<=o;j++)
				if (i%n!=j%n) 
					cout<<i<<" "<<j<<'\n';
		return;
	}
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) 
			f[i][j]=0;
	int lst=0;
	int tot=0;
	int mx=0,mxtim=0;
	ull seed=gen();
	mt19937_64 rnd(seed);
	for (int tms=0;tms<=1000000;tms++)
	{
		if (id==3&&mx>=2*n)
		{
			mxtim=tms;
			break;
		}
		if (tot>mx)
		{
			mx=tot,mxtim=tms;
		}
		
		if (lst>=2000)
		{
			int x,y;
			x=rnd()%n+1,y=rnd()%n+1;
			while (x==y||!f[x][y]) 
				x=rnd()%n+1,y=rnd()%n+1;
			f[x][y]=f[y][x]=0;
			G[x].erase(find(G[x].begin(),G[x].end(),y));
			G[y].erase(find(G[y].begin(),G[y].end(),x));
			lst=0;
			tot--;
			continue;
		}
		int x,y;
		x=rnd()%n+1,y=rnd()%n+1;
		while (x==y||f[x][y]) 
			x=rnd()%n+1,y=rnd()%n+1;
		for (auto u:G[y])
			col[u]=1;
		bool bl=1;
		for (auto u:G[x])
		{
			for (auto v:G[u])
				if (col[v]) bl=0;
		}
		if (bl)
		{
			f[x][y]=1;
			f[y][x]=1;
			G[x].push_back(y);
			G[y].push_back(x);
			tot++;
		} else lst++;
		for (auto u:G[y]) col[u]=0;
	}

	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) 
			f[i][j]=0;
	for (int i=1;i<=n;i++)	poly().swap(G[i]);

	mt19937_64 rnd1(seed);
	lst=0;tot=0;
	for (int tms=0;tms<mxtim;tms++)
	{
		if (lst>=2000)
		{
			int x,y;
			x=rnd1()%n+1,y=rnd1()%n+1;
			while (x==y||!f[x][y]) 
				x=rnd1()%n+1,y=rnd1()%n+1;
			f[x][y]=f[y][x]=0;
			G[x].erase(find(G[x].begin(),G[x].end(),y));
			G[y].erase(find(G[y].begin(),G[y].end(),x));
			lst=0;
			tot--;
			// cout<<"Ers "<<x<<" "<<y<<endl;
			continue;
		}
		int x,y;
		x=rnd1()%n+1,y=rnd1()%n+1;
		while (x==y||f[x][y]) 
			x=rnd1()%n+1,y=rnd1()%n+1;
		for (auto u:G[y])
			col[u]=1;
		bool bl=1;
		for (auto u:G[x])
		{
			for (auto v:G[u])
				if (col[v]) bl=0;
		}
		if (bl)
		{
			f[x][y]=1;
			f[y][x]=1;
			G[x].push_back(y);
			G[y].push_back(x);
			tot++;
		} else lst++;
		for (auto u:G[y]) col[u]=0;
	}
	
	tot=0;
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++)
			if (f[i][j]) tot++;
	cout<<n<<" "<<tot<<'\n';
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++)
			if (f[i][j])
			{
				cout<<i<<" "<<j<<'\n';
				f[i][j]=f[j][i]=0;
			}
	for (int i=1;i<=n;i++) poly().swap(G[i]);
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;cin>>T>>id;
	while (T--)
	{
		BellaKira();
	}
}