#include <bits/stdc++.h> using namespace std; const int N = 3e5 + 5; template <typename _T> inline void read(_T &x) { x = 0; static char c; c = getchar(); bool f = 0; for (; c < '0' || c > '9'; c = getchar()) f |= (c == '-'); for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + (c ^ 48); x = (f) ? (-x) : x; } struct edge { int y, u; }; int op, n, m; vector<edge> E[N]; int fa[N]; int get(int x) { if (x == fa[x]) return x; return fa[x] = get(fa[x]); } int ecnt[N], Um[N], Vm[N]; int vis[N * 2]; struct edge2 { int y, a, b, u; }; vector<edge2> G[N]; vector<edge> F[N]; int dfn[N], tim = 0, t = 0; int deg[N], fa2[N]; int get2(int x) { if (x == fa2[x]) return x; return fa2[x] = get2(fa2[x]); } void app(int x, int y, int a, int b) { ++t; fa2[get2(x)] = get2(y); // cout<<x<<'-'<<y<<endl; G[x].push_back((edge2){ y, a, b, t }); G[y].push_back((edge2){ x, b, a, t }); deg[x]++; deg[y]++; } bool dfs(int x, edge v) { dfn[x] = ++tim; for (auto u : E[x]) { int y = u.y; if (!dfn[y]) { if (!dfs(y, (edge){ x, u.u })) F[x].push_back(u); } else if (dfn[y] < dfn[x] && v.u != u.u) F[y].push_back((edge){ x, u.u }); } if (F[x].size() % 2 == 0) { for (int i = 0; i < F[x].size(); i += 2) app(F[x][i].y, F[x][i + 1].y, F[x][i].u, F[x][i + 1].u); return 0; } F[x].push_back(v); for (int i = 0; i < F[x].size(); i += 2) app(F[x][i].y, F[x][i + 1].y, F[x][i].u, F[x][i + 1].u); return 1; } int cur[N]; struct Path { int s, t; vector<int> p; }; vector<Path> Ans; edge2 ans[N * 2]; int K = 0; void eular(int x) { for (int &i = cur[x]; i < (int)G[x].size(); i++) if (!vis[G[x][i].u]) { vis[G[x][i].u] = 1; auto v = G[x][i]; eular(v.y); ans[++K] = v; } } vector<int> Tu[N]; void cons_eular(int rt) { if (Tu[rt].size() == 1) return; bool f = 1; G[n + 1].clear(); for (int x : Tu[rt]) { f &= (deg[x] % 2 == 0); if (deg[x] & 1) { app(x, n + 1, 0, 0); } } K = 0; cur[n + 1] = 0; if (f) { eular(rt); reverse(ans + 1, ans + K + 1); Path now; now.s = now.t = rt; // cout<<now.s<<' '<<now.t<<endl; for (int i = 1; i <= K; i++) { now.p.push_back(ans[i].a); // cout<<ans[i].a<<'='<<ans[i].b<<'='; if (ans[i].a != ans[i].b) now.p.push_back(ans[i].b); } // cout<<endl; Ans.push_back(now); } else { eular(n + 1); reverse(ans + 1, ans + K + 1); for (int i = 1; i < K; i++) { int j = i; while (j + 1 <= K && ans[j + 1].y != n + 1) j++; Path now; now.s = ans[i].y; now.t = ans[j].y; for (int k = i + 1; k <= j; k++) { now.p.push_back(ans[k].a); // cout<<ans[k].a<<'='<<ans[k].b<<'='; if (ans[k].a != ans[k].b) now.p.push_back(ans[k].b); } // cout<<endl; Ans.push_back(now); i = j + 1; } } } void construct(int rt) { dfs(rt, (edge){ 0, 0 }); } int used[N], used2[N]; bool chk() { for (int i = 1; i <= n; i++) used[i] = 0; for (int i = 1; i <= m; i++) used2[i] = 0; for (auto U : Ans) { if (U.s == U.t) { if (used[U.s]) return 0; used[U.s] = 1; } else { if (used[U.s]) return 0; if (used[U.t]) return 0; } used[U.s] = 1; used[U.t] = 1; if (U.p.size() == 0) return 0; if (op == 1 && U.p.size() % 2 == 1) return 0; int cur = U.s; for (int j = 0; j < (int)U.p.size(); j++) { int id = U.p[j]; if (used2[id]) return 0; used2[id] = 1; if (Um[id] != cur && Vm[id] != cur) return 0; cur = Um[id] + Vm[id] - cur; } if (cur != U.t) return 0; } for (int i = 1; i <= m; i++) if (!used2[i]) return 0; return 1; } int test = 0; void solve() { ++test; read(n); read(m); Ans.clear(); Ans.shrink_to_fit(); for (int i = 1; i <= t; i++) vis[i] = 0; t = 0; for (int i = 1; i <= n; i++) G[i].clear(), vis[i] = 0, E[i].clear(), F[i].clear(), deg[i] = cur[i] = 0, Tu[i].clear(); for (int i = 1; i <= n; i++) fa[i] = fa2[i] = i, ecnt[i] = 0, dfn[i] = 0; for (int i = 1; i <= m; i++) { int x, y; read(x); read(y); E[x].push_back({ y, i }); E[y].push_back({ x, i }); fa[get(x)] = get(y); Um[i] = x; Vm[i] = y; if (op == 0) app(x, y, i, i); } for (int i = 1; i <= m; i++) ecnt[get(Um[i])]++; if (op == 1) { for (int i = 1; i <= n; i++) if (get(i) == i) { if (ecnt[i] & 1) { printf("-1\n"); return; } construct(i); } } for (int i = 1; i <= n; i++) Tu[get2(i)].push_back(i); for (int i = 1; i <= n; i++) if (get2(i) == i) cons_eular(i); assert(chk()); printf("%d\n", (int)Ans.size()); for (auto U : Ans) { printf("%d %d %d\n", U.s, U.t, (int)U.p.size()); for (int u : U.p) printf("%d ", u); printf("\n"); } } int main() { int T; read(T); read(op); while (T--) { solve(); } return 0; }