#include<bits/stdc++.h>
using namespace std;using ll=long long;
int rd(int x=0,char c=getchar()){int f=1;while(!isdigit(c))f=(c^'-'?1:-1),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x*f;}
const int N=4e5+5;
int n,m;
int F[N];int getf(int x){return F[x]==x?x:F[x]=getf(F[x]);}
int id(int x,int y){return (x-1)*n+y;}
vector<int> E[N];
vector<int> s;
int fl;
void dfs(int u,int fa,int to){
//	cout<<u<<endl;
	if(fl)return;
	s.push_back(u);
	if(u==to)return fl=1,void();
	for(int v:E[u]){
		if(fl)return;
		if(v^fa)dfs(v,u,to);
	}
	if(fl)return;
	s.pop_back();
}
void solve(){
	n=rd(),m=rd();
	int k=(m-1)/(n-1)+1;
	for(int i=1;i<=k;i++)for(int j=1;j<=n;j++)E[id(i,j)].clear(),F[id(i,j)]=id(i,j);
	for(int i=1;i<=m;i++){
		int u=rd(),v=rd();
		int l=1,r=k,p=1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(getf(id(mid,u))!=getf(id(mid,v)))p=mid,r=mid-1;
			else l=mid+1;
		}
		E[id(p,u)].push_back(id(p,v));
		E[id(p,v)].push_back(id(p,u));
		F[getf(id(p,v))]=getf(id(p,u));
	}
	int u,v;
	for(int i=1;i<=n;i++)if(E[id(k,i)].size()){u=id(k,i),v=E[id(k,i)][0];break;}
//	for(int i=1;i<=k;i++){
//		cout<<i<<" th\n"<<endl;
//		for(int j=1;j<=n;j++)for(int x:E[id(i,j)])cout<<id(i,j)<<" <-> "<<x<<endl;
//		puts("");
//	}
	u=u-id(k,1)+1,v=v-id(k,1)+1;
	printf("%d %d\n",u,v);
	for(int i=1;i<=k;i++){
//		cout<<i<<" th:\n";
		s.clear();fl=0;
		dfs(id(i,u),0,id(i,v));
		printf("%d ",s.size());
		for(int X:s)printf("%d ",X-id(i,1)+1);
		puts("");
	}
}
int main(){
	int t=rd();while(t--)solve();
	return 0;
}
/*
1
4 7
1 2
2 3
3 4
4 1
1 3
2 4
1 4
*/