#include<bits/stdc++.h>
using namespace std;
struct dsu{
	vector <int> fa;
	void init(int n){for(int i=0;i<=n;i++) fa[i]+=i;}
	int find(int x){return fa[x]!=x?fa[x]=find(fa[x]):x;}
};
int t,n,m,k,u,v,l,r;
basic_string <int> K,G[100001];
int dfs(int x,int u,int v){
	if(x==v) return 1;
	for(int y:G[x]){
		if(y==u) continue;
		if((K+=y,1)&&dfs(y,x,v)) return 1;
		K.pop_back();
	}
	return 0;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m),k=(m-1)/(n-1)+1;
		vector <dsu> s(k+1);
		vector <vector<pair<int,int>>> p(k+1);
		for(int i=1;i<=k;i++) s[i].init(n);
		for(int i=1;i<=m;i++){
			scanf("%d%d",&u,&v),l=1,r=k+1;
			while(l<r){
				int mid=(l+r)/2;
				if(s[mid].find(u)==s[mid].find(v)) l=mid+1;
				else r=mid;
			}
			if(l<=k) s[l].fa[s[l].find(u)]=s[l].find(v),p[l].push_back({l,r});
		}
		auto [x,y]=p[k][0];
		for(int i=k;i>=1;i--,printf("\n")){
			for(auto [u,v]:p[i]) G[u].clear(),G[v].clear();
			for(auto [u,v]:p[i]) G[u]+=v,G[v]+=u;
			K.clear(),K+=u,dfs(x,0,y),printf("%d ",K.size());
			for(int j:K) printf("%d ",j);
		}
	}
	return 0;
}