#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v #define mk make_pair #define pb push_back const int MAXN=600010; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} struct Edge{int v,nx,w;}edge[MAXN<<1];int h[MAXN],CNT; void add_side(int u,int v){edge[++CNT]={v,h[u],-1};h[u]=CNT;edge[++CNT]={u,h[v],-1};h[v]=CNT;} void add_side(int u,int v,int w){edge[++CNT]={v,h[u],w};h[u]=CNT;edge[++CNT]={u,h[v],w};h[v]=CNT;} int n,m,op,cnt,dep[MAXN],d[MAXN]; struct side{int u,v,w;}s[MAXN]; bool dfs(int u,int lst){ dep[u]=dep[lst]+1; vector<int>G;G.clear(); int sum=0; for(inx(u))if(!dep[v]){ if(dfs(v,u))G.pb(v); } else if(dep[v]>dep[u])G.pb(v); int res=1; if(G.size()&1)G.pb(lst),res=0; for(int i=0;i<G.size();i+=2)s[++cnt]={G[i],G[i+1],u};//,cout<<G[i]<<" "<<G[i+1]<<" "<<u<<endl; return res; } #define inx2(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=h[(u)],v=edge[I].v,w=edge[I].w side p[MAXN];int tot; void ola(int u){ for(inx2(u)){ h[u]=edge[I].nx; if(!w)continue; edge[I].w=edge[I^1].w=0; ola(v); p[++tot]={v,u,w}; d[u]--,d[v]--; } } int k; vector<int>as[MAXN]; map<pii,int>mp; void slv(){ n=read(),m=read(); for(int i=1;i<=n+2;i++)h[i]=d[i]=dep[i]=0;CNT=k=1,tot=cnt=0; mp.clear(); for(int i=1;i<=m;i++){ int u=read(),v=read(); // cout<<u<<" "<<v<<" "<<i<<endl; add_side(u,v); mp[mk(u,v)]=mp[mk(v,u)]=i; d[u]++,d[v]++; } if((m&1)&&op){printf("-1\n");return;} else if(!op){ for(int i=1;i<=n;i++)if(d[i]&1)add_side(n+1,i,-2),d[i]++,d[n+1]++; ola(n+1); for(int i=2;i<=tot;i++){ if(p[i].w==-2){ as[k].pb(p[i].u),i++,k++; continue; } as[k].pb(p[i].u); } for(int i=1;i<=n;i++)if(d[i]){ tot=0; ola(i); for(int j=1;j<=tot;j++){ as[k].pb(p[j].u); } as[k].pb(p[cnt].v); k++; } k--; printf("%lld\n",k); for(int i=1;i<=k;i++){ printf("%lld %lld %lld\n",as[i][0],as[i][as[i].size()-1],as[i].size()-1); for(int o=0;o<as[i].size()-1;o++)printf("%lld ",mp[mk(as[i][o],as[i][o+1])]); printf("\n"); as[i].clear(); } return; } for(int i=1;i<=n;i++)if(!dep[i])if(!dfs(i,i)){printf("-1\n");return;} for(int i=1;i<=n+2;i++)h[i]=d[i]=0;CNT=1; for(int i=1;i<=cnt;i++)d[s[i].u]++,d[s[i].v]++,add_side(s[i].u,s[i].v,s[i].w); for(int i=1;i<=n;i++)if(d[i]&1)add_side(n+1,i,-1),d[i]++,d[n+1]++; ola(n+1); for(int i=2;i<=tot;i++){ if(p[i].w==-1){ as[k].pb(p[i].u),i++,k++; as[k].clear(); continue; } as[k].pb(p[i].u); as[k].pb(p[i].w); } // for(int i=1;i<=n;i++)cout<<d[i]<<" ";cout<<endl; for(int i=1;i<=n;i++)if(d[i]){ tot=0; ola(i); for(int j=1;j<=tot;j++){ as[k].pb(p[j].u); as[k].pb(p[j].w); } as[k].pb(p[tot].v); k++; } k--; printf("%lld\n",k); for(int i=1;i<=k;i++){ printf("%lld %lld %lld\n",as[i][0],as[i][as[i].size()-1],as[i].size()-1); for(int o=0;o<as[i].size()-1;o++)printf("%lld ",mp[mk(as[i][o],as[i][o+1])]); printf("\n"); as[i].clear(); } } signed main(){ int _=read();op=read();while(_--) slv(); return 0; }