#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; using namespace std; const int maxn=3e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int OP,n,m; vector<pi>E[maxn],fz[maxn]; pi R[maxn],A[maxn]; struct node { int S,T; vector<int>P; void MOD(int op){ if(!op){ for(int &x:P)if(x>m)x-=m; return; } vector<int>Q; for(int x:P){ Q.p_b(R[x].p1),Q.p_b(R[x].p2); }P.swap(Q); } }; struct Graph { vector<pi>E[maxn]; vector<int>P; bool vis[maxn]; void dfs(int u,int fa=-1){ while(E[u].size()){ auto it=E[u].back();E[u].pop_back(); if(vis[it.p2-(it.p2>m)*m])continue; vis[it.p2-(it.p2>m)*m]=1; dfs(it.p1,it.p2); } if(fa!=-1)P.p_b(fa); } int calc(pi a,pi b){ map<int,int>mp; mp[a.p1]++,mp[a.p2]++,mp[b.p1]++,mp[b.p2]++; for(auto it:mp)if(it.p2==2)return it.p1; return -1; } void get_Path(int u,vector<pair<pi,int> >e,vector<node>&Path){Path.clear(); if(e.empty())return; for(auto it:e)E[it.p1.p1].clear(),E[it.p1.p2].clear(); for(auto it:e)E[it.p1.p1].p_b(m_p(it.p1.p2,it.p2)); bool ban=1; if(E[u].empty())ban=0,u=e[0].p1.p1; P.clear();dfs(u); up(i,0,(int)P.size()-1){ int j=i; while(j<(int)P.size()&&((A[P[j]].p1!=u&&A[P[j]].p2!=u)||(!ban)))j++;j--; if(j==i-1)continue; node X; if(i==j)X.S=A[P[i]].p1,X.T=A[P[i]].p2; else X.S=A[P[i]].p1+A[P[i]].p2-calc(A[P[i]],A[P[i+1]]),X.T=A[P[j]].p1+A[P[j]].p2-calc(A[P[j]],A[P[j-1]]); X.P.clear();up(w,i,j)X.P.p_b(P[w]); Path.p_b(X); i=j+1; } } }T; bool vis[maxn]; vector<int>P; void dfs(int u){ vis[u]=1;P.p_b(u); for(auto it:E[u])if(vis[it.p1])fz[it.p1].p_b(m_p(u,it.p2));else dfs(it.p1); } void slv(){ n=read(),m=read(); up(i,1,n)vis[i]=0,E[i].clear(),fz[i].clear(); up(i,1,m){ int x=read(),y=read(); A[i]=m_p(x,y);A[i+m]=m_p(y,x); E[x].p_b(m_p(y,i)),E[y].p_b(m_p(x,i+m)); } vector<node>ans; up(i,1,n)if(!vis[i]){ P.clear();dfs(i); if(!OP){ vector<pair<pi,int> >e; for(int x:P)for(auto it:E[x])e.p_b(m_p(m_p(x,it.p1),it.p2)); int p=0; for(int x:P)if(E[x].size()&1)++p,e.p_b(m_p(m_p(n+1,x),m*2+p)),A[m*2+p]=m_p(n+1,x); vector<node>v; T.get_Path(n+1,e,v); for(auto &x:v)x.MOD(OP); for(auto x:v)ans.p_b(x); }else assert(0); }printf("%d\n",(int)ans.size()); for(auto it:ans){ printf("%d %d %d\n",it.S,it.T,(int)it.P.size()); for(int x:it.P)printf("%d ",x);printf("\n"); } } int main(){ //freopen("run.in","r",stdin); //freopen("run.out","w",stdout); int t=read();OP=read();while(t--)slv(); fclose(stdin); fclose(stdout); return 0; }