#include<bits/stdc++.h>

#define INF 1e18
#define int long long
#define maxn 100005

using namespace std;

inline int read(){
	int lre=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		lre=(lre<<3)+(lre<<1)+(c-'0');
		c=getchar();
	}
	return lre*f;
} 

struct edge{
	int to;
	int val;
	int next;
}e[4*maxn];

int e_cnt=1,head[maxn];

int add(int u,int v,int w){
	e[e_cnt].to=v;
	e[e_cnt].val=w;
	e[e_cnt].next=head[u];
	head[u]=e_cnt++;
}

int n,m;
vector<vector<int> > root;
vector<int> V;
map<int,int> mp;

bool okay=false;
bool visited[maxn];
vector<int> ans;//遍历路径 

int f_f(int x,int y){
	if(root[y][x]!=x){
		root[y][x]=f_f(root[y][x],y);
	}
	return root[y][x];
}

void merge(int u,int v,int y){
	root[y][f_f(u,y)]=f_f(v,y);
}

void dfs(int x,int color,int goal){
//	cout<<"x="<<x<<endl;
	visited[x]=true;
	ans.push_back(x);
	if(x==goal){
		okay=true;
		printf("%lld ",ans.size());
		for(int i=0;i<ans.size();++i){
			printf("%lld ",ans[i]);
		}
		putchar('\n');
	}else{
		for(int i=head[x];i;i=e[i].next){
			int v=e[i].to,w=e[i].val;
			if(w!=color)continue;
			if(visited[v])continue;
			dfs(v,color,goal);
			if(okay)break;
		}
	}
	visited[x]=false;
	ans.pop_back();
}

void solve(){
	V.clear();root.clear();e_cnt=1;
	n=read();m=read();
	for(int i=0;i<=n;i++){
		V.push_back(i);head[i]=0;
		visited[i]=false;
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		if(root.empty()||f_f(u,root.size()-1)==f_f(v,root.size()-1)){
		//	cout<<"new!"<<endl;
			root.push_back(V);
			merge(u,v,root.size()-1);
			add(u,v,root.size()-1);
			add(v,u,root.size()-1); 
		}else{
			int l=0,r=root.size()-1,mid,ind;
			while(l<=r){
				mid=l+r>>1;
				if(f_f(u,mid)==f_f(v,mid)){
					l=mid+1;
				}else{
					ind=mid;
					r=mid-1;
				}
			}
		//	cout<<"merge in "<<ind<<endl;
			merge(u,v,ind);
			add(u,v,ind);add(v,u,ind);
		}
	}
	mp.clear();
	int x,y;
	for(int i=1;i<=n;i++){
		x=f_f(i,root.size()-1);
		if(mp[x]==0){
			mp[x]=i;
		}else{
			y=mp[x];
			break;
		}
	}
	swap(x,y);
	printf("%lld %lld\n",x,y);
//	cout<<"k="<<(n+m-2)/(n-1)<<endl;
	for(int i=0;i<(m+n-2)/(n-1);i++){
		okay=false;
		dfs(x,i,y);
	}
}

signed main(){
	int t=read();
	while(t--){
		solve();
	}
	return 0;
}
/*

*/