#include<bits/stdc++.h>

#define maxn 200008
#define pii pair<int,int>
#define int long long

using namespace std;

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

inline int f(int a,int b){
	return (a<<32)|b;
} 

int T;
int n,m,s,t;
map<int,set<int> > ga[maxn];
map<int,int> mp;

void add(int u,int v,int y){
	mp[f(u,v)]++;
	ga[u][y].insert(v);
}

void del(int u,int v,int y){
	mp[f(u,v)]--;
	if(mp[f(u,v)]==0)ga[u][y].erase(ga[u][y].find(v));
}

int cnt=0;
map<int,map<int,int> > root;

int f_f(int x,int y){
	if(root[y][x]==0)root[y][x]=x;
	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){
	if(root[y][u]==0)root[y][u]=u;
	if(root[y][v]==0)root[y][v]=v;
	root[y][f_f(u,y)]=f_f(v,y);
}

bool okay=false;
vector<int> v;
bool visited[maxn];

void dfs(int x,int goal,int y){
//	cout<<"x="<<x<<endl;
	v.push_back(x);visited[x]=true;
	if(x==goal){
		printf("%lld ",v.size());
		for(int i:v){
			printf("%lld ",i);
		} 
		putchar('\n');
		okay=true;
	}else{
		set<int>::iterator it;
		for(it=ga[x][y].begin();it!=ga[x][y].end();it++){
			int v=*it;
			if(visited[v])continue;
		//	cout<<x<<"->"<<v<<endl;
			dfs(v,goal,y);
			if(okay){
				del(x,v,y);del(v,x,y);
				break;
			}
		}
	}
	v.pop_back();visited[x]=false;
}

void solve(){
	n=read();m=read();
//	cout<<"new!!!!!!!!!!!!!!!!!!!!!n="<<n<<" m="<<m<<"!!!!!"<<endl;
	mp.clear();cnt=0;root.clear(); 
	for(int i=1;i<=n;i++){
		ga[i].clear(); 
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
	//	cout<<"fu="<<f_f(u,cnt)<<" fv="<<f_f(v,cnt)<<endl; 
		if(cnt==0||f_f(u,cnt)==f_f(v,cnt)){
		//	cout<<"new!"<<endl; 
			cnt++;merge(u,v,cnt);
			add(u,v,cnt);add(v,u,cnt);
		}else{
			int l=1,r=cnt,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;
				}
			}
			merge(u,v,ind);
			add(u,v,ind);add(v,u,ind);
		}
	}
//	cout<<"cnt="<<cnt<<endl; 
	for(int i=1;i<=n;i++){
		if(f_f(i,cnt)!=i){
			s=i;t=f_f(i,cnt);
			break;
		}
	}
//	cout<<"res:";
	printf("%lld %lld\n",s,t);
	int k=(m+n-2)/(n-1);
//	cout<<"k="<<k<<endl;
	for(int i=1;i<=k;i++){
	//	cout<<"No "<<i<<".";
		okay=false;
		dfs(s,t,i);
	}
}

signed main(){
	
//	freopen("3.in","r",stdin);
	
	memset(visited,0,sizeof(visited));
	
	T=read();
	while(T--){
	//	cout<<"t="<<T<<endl;
		solve();
	} 
	
	return 0;
}