#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,type;
int N,M;

int readtrash(){
	int n,m,p,q;
	scanf("%d%d",&n,&m);
	rep(i,1,m) scanf("%d%d",&p,&q);
	return n;
}

vector <pii> ans;
void solve1(int k){
	scanf("%d%d",&N,&M);
	ans.clear();
	rep(u,1,N){
		rep(v,u + 1,N) if(u % k != v % k) ans.eb(mkp(u,v));
	}	
	printf("%d %d\n",N,SZ(ans));
	for(pii I:ans) printf("%d %d\n",I.first,I.second);
	assert(SZ(ans) >= M);
}

int main(){
	scanf("%d%d",&T,&type);
	if(type <= 2){
		while(T--) solve1(readtrash() - 1);
	}
	return 0;
}