#include<bits/stdc++.h>
using namespace std;
const int NN=2e5+10,N=1e5+10;
const int K=2e5+10;
struct E
{
int fr,to,ct;
}inp[NN];
struct A
{
int fr,to,lt,nt;
int ct;
}e[NN*2];
vector<vector<int>>ee[K];
int ans1[K];
int b[N];
int n,m;
void push(int fr,int to,int ct)
{
b[0]++;e[b[0]].to=to;e[b[0]].fr=fr;e[b[0]].lt=b[fr];e[b[fr]].nt=b[0];e[b[0]].nt=0;b[fr]=b[0];
e[b[0]].ct=ct;
}
void add(int fr,int to,int ct)
{
push(fr,to,ct);push(to,fr,ct);
}
void del1(int num,int d)
{
e[num].ct-=d;
if(e[num].ct<=0)
{
int nt=e[num].nt,lt=e[num].lt;
if(nt) e[nt].lt=lt;
if(lt) e[lt].nt=nt;
}
}
void del(int num,int d)
{
del1(num,d);del1(num^1,d);
}
bool ss(E t1,E t2)
{
return t1.fr<t2.fr||(t1.fr==t2.fr&&t1.to<t2.to);
}
queue<int>q;
int du[N];
int totn,totm;
bool vis[N];
void dfs(int now)
{
vis[now]=1;
totn++;totm+=du[now];
for(int i=b[now];i;i=e[i].lt)
if(!vis[e[i].to]) dfs(e[i].to);
}
int node[N],siz;
queue<int> qq;
int dfs1(int now)
{
int mx=0;
vis[now]=1;
q.push(now);
for(int i=b[now];i;i=e[i].lt)
if(!vis[e[i].to])
{
qq.push(i);
mx=max(mx,e[i].ct);
mx=max(mx,dfs1(e[i].to));
}
return mx;
}
void dfs2(int now)
{
q.push(now);
vis[now]=1;
for(int i=b[now];i;i=e[i].lt)
if(!vis[e[i].to]) dfs2(e[i].to);
}
void work(int k)
{
if(!k) return;
siz=0;
while(!q.empty())
{
++siz;
node[siz]=q.front();q.pop();
}
for(int i=1;i<=siz;i++) vis[node[i]]=0;
int mxk=0,root=0;
for(int i=1;i<=siz;i++)
if(!vis[node[i]])
{
totn=0,totm=0;
dfs(node[i]);
int tmpk=(totm+totn-2)/(totn-1);
if(tmpk>=mxk)
{
root=node[i];
mxk=tmpk;
}
}
for(int i=1;i<=siz;i++) vis[node[i]]=0;
int num=dfs1(root);
ans1[k]=num;
while(!qq.empty())
{
int now=qq.front();qq.pop();
del(now,num);
ee[e[now].fr][k].push_back(e[now].to);
ee[e[now].to][k].push_back(e[now].fr);
}
for(int i=1;i<=siz;i++) vis[node[i]]=0;
dfs2(root);
work(k-1);
}
int s[N],top;
int lay;
void dfss(int now,int end,int fa)
{
s[++top]=now;
if(now==end)
{
cout<<top<<' ';
for(int i=1;i<=top;i++) cout<<s[i]<<' ';
cout<<endl;
}
int tmp=ee[now][lay].size();
for(int i=0;i<tmp;i++)
{
int to=ee[now][lay];
if(to!=fa)
{
dfs(to,end,now);
}
}
s[top--]=0;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin>>T;
while(T--){
while(!q.empty())q.pop();
cin>>n>>m;
for(int i=0;i<=n;i++) b[0]=0;
for(int i=1;i<=n;i++) du[i]=0;
b[0]=1;
for(int i=1;i<=m;i++)
{
cin>>inp[i].fr>>inp[i].to;
inp[i].ct=1;
}
sort(inp+1,inp+m+1,ss);
for(int i=1;i<=m;i++)
{
if(inp[i].fr==inp[i-1].fr&&inp[i].to==inp[i-1].to) inp[i].ct+=inp[i-1].ct;
else
{
add(inp[i-1].fr,inp[i-1].to,inp[i-1].ct);
}
for(int i=1;i<=n;i++) q.push(i);
int k=(m+n-1-1)/(n-1);
for(int i=1;i<=n;i++) ee[i].resize(k+1);
work(k);
int u=q.front();q.pop();
int v=q.front();q.pop();
for(int i=1;i<=k;i++)
{
lay=i;
for(int j=1;j<=ans1[i];j++) dfss(u,v,u);
}
}
}
return 0;
}