Cycle Closing

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

vector<int> directLine(int s, int t, int len) {
    if (s == t) return len == 0 ? vector<int>{s} : vector<int>{};
    if (s > t) {
        auto res = directLine(t, s, len);
        reverse(res.begin(), res.end());
        return res;
    }
    int d = t - s;
    if ((d + 1) / 2 > len || len > d) return {};
    int twos = d - len;
    vector<int> res{s};
    int cur = s;
    for (int i = 0; i < twos; i++) {
        cur += 2;
        res.push_back(cur);
    }
    while (cur < t) {
        cur++;
        res.push_back(cur);
    }
    return res;
}

vector<int> leftGadget(int p, int waste) {
    if (waste == 0) return {p, p + 1};
    vector<int> res{p};
    if (waste % 2 == 0) {
        for (int x = p - 2; x >= p - waste; x -= 2) res.push_back(x);
        res.push_back(p - waste + 1);
        for (int x = p - waste + 3; x <= p + 1; x += 2) res.push_back(x);
    } else {
        for (int x = p - 2; x >= p - (waste - 1); x -= 2) res.push_back(x);
        res.push_back(p - waste);
        for (int x = p - waste + 2; x <= p + 1; x += 2) res.push_back(x);
    }
    return res;
}

vector<int> rightGadget(int p, int waste) {
    if (waste == 0) return {p, p + 1};
    vector<int> res{p};
    if (waste % 2 == 1) {
        for (int x = p + 2; x <= p + waste + 1; x += 2) res.push_back(x);
        res.push_back(p + waste);
        for (int x = p + waste - 2; x >= p + 1; x -= 2) res.push_back(x);
    } else {
        for (int x = p + 2; x <= p + waste; x += 2) res.push_back(x);
        res.push_back(p + waste + 1);
        for (int x = p + waste - 1; x >= p + 1; x -= 2) res.push_back(x);
    }
    return res;
}

vector<int> linePath(int D, int s, int t, int len) {
    if (s == t) return len == 0 ? vector<int>{s} : vector<int>{};
    if (s > t) {
        auto res = linePath(D, t, s, len);
        reverse(res.begin(), res.end());
        return res;
    }

    auto direct = directLine(s, t, len);
    if (!direct.empty()) return direct;

    int d = t - s;
    if (len < d) return {};
    int waste = len - d;

    if (d == 1) {
        if (waste <= s) return leftGadget(s, waste);
        if (waste <= D - t) return rightGadget(s, waste);
        return {};
    }

    int low = max(0, waste - (D - t));
    int high = min(waste, s);
    if (low > high) return {};

    int leftWaste = low;
    int rightWaste = waste - leftWaste;

    vector<int> res = leftGadget(s, leftWaste);
    for (int x = s + 2; x < t; x++) res.push_back(x);
    auto tail = rightGadget(t - 1, rightWaste);
    res.insert(res.end(), tail.begin() + 1, tail.end());
    return res;
}

int main() {
    setIO();

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<vector<int>> orig(n, vector<int>(n, 0));
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            --u; --v;
            orig[u][v] = orig[v][u] = 1;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        if (m == n * (n - 1) / 2) {
            cout << 0 << '\n';
            continue;
        }

        vector<vector<int>> tree(n);
        vector<int> seen(n, 0);
        queue<int> q;
        seen[0] = 1;
        q.push(0);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : g[u]) {
                if (!seen[v]) {
                    seen[v] = 1;
                    tree[u].push_back(v);
                    tree[v].push_back(u);
                    q.push(v);
                }
            }
        }

        const int INF = 1e9;
        vector<vector<int>> dist(n, vector<int>(n, INF));
        vector<vector<int>> prv(n, vector<int>(n, -1));
        for (int s = 0; s < n; s++) {
            queue<int> bfs;
            dist[s][s] = 0;
            prv[s][s] = s;
            bfs.push(s);
            while (!bfs.empty()) {
                int u = bfs.front();
                bfs.pop();
                for (int v : tree[u]) {
                    if (dist[s][v] == INF) {
                        dist[s][v] = dist[s][u] + 1;
                        prv[s][v] = u;
                        bfs.push(v);
                    }
                }
            }
        }

        auto treePath = [&](int u, int v) {
            vector<int> res;
            int x = v;
            while (x != u) {
                res.push_back(x);
                x = prv[u][x];
            }
            res.push_back(u);
            reverse(res.begin(), res.end());
            return res;
        };

        auto pathWithLen = [&](const vector<int>& p, int need) {
            if (need == 0) return vector<int>{p[0]};
            int d = (int)p.size() - 1;
            vector<int> res{p[0]};
            int idx = 0;
            int twos = d - need;
            for (int i = 0; i < twos; i++) {
                idx += 2;
                res.push_back(p[idx]);
            }
            while (idx < d) {
                idx++;
                res.push_back(p[idx]);
            }
            return res;
        };

        int A = 0;
        for (int i = 0; i < n; i++) if (dist[0][i] > dist[0][A]) A = i;
        int B = A;
        for (int i = 0; i < n; i++) if (dist[A][i] > dist[A][B]) B = i;

        vector<int> diameter = treePath(A, B);
        int D = (int)diameter.size() - 1;
        int L = (D + 1) / 2;

        vector<int> cpos(n), cnode(n);
        for (int x = 0; x < n; x++) {
            int best = 0;
            for (int i = 1; i <= D; i++) {
                if (dist[x][diameter[i]] < dist[x][diameter[best]]) best = i;
            }
            cpos[x] = best;
            cnode[x] = diameter[best];
        }

        function<vector<int>(int,int,int)> makePath = [&](int u, int v, int need) -> vector<int> {
            if (need == 0) return {u};

            if (dist[u][v] >= need) {
                return pathWithLen(treePath(u, v), need);
            }

            if (cpos[u] != cpos[v]) {
                bool rev = false;
                if (cpos[u] > cpos[v]) {
                    swap(u, v);
                    rev = true;
                }

                int hu = dist[u][cnode[u]];
                int hv = dist[v][cnode[v]];
                for (int ru = hu; ru >= (hu + 1) / 2; ru--) {
                    for (int rv = hv; rv >= (hv + 1) / 2; rv--) {
                        int rem = need - ru - rv;
                        if (rem < 1) continue;
                        auto mid = linePath(D, cpos[u], cpos[v], rem);
                        if (mid.empty()) continue;

                        vector<int> left = hu ? pathWithLen(treePath(u, cnode[u]), ru) : vector<int>{u};
                        vector<int> right = hv ? pathWithLen(treePath(cnode[v], v), rv) : vector<int>{v};

                        vector<int> res = left;
                        for (int i = 1; i < (int)mid.size(); i++) res.push_back(diameter[mid[i]]);
                        for (int i = 1; i < (int)right.size(); i++) res.push_back(right[i]);
                        if (rev) reverse(res.begin(), res.end());
                        return res;
                    }
                }
                return vector<int>{};
            }

            int c = cnode[u];
            auto isAncestor = [&](int a, int b) {
                return dist[c][b] == dist[c][a] + dist[a][b];
            };

            if (u != v && isAncestor(v, u)) {
                auto res = makePath(v, u, need);
                reverse(res.begin(), res.end());
                return res;
            }

            if (!isAncestor(u, v)) {
                auto up = treePath(u, c);
                int p = up[1];
                auto rest = makePath(p, v, need - 1);
                vector<int> res{u};
                res.insert(res.end(), rest.begin(), rest.end());
                return res;
            }

            array<int, 2> ends = {A, B};
            for (int e : ends) {
                auto line = treePath(e, v);
                int s = dist[e][u];
                int t = (int)line.size() - 1;
                if (s < 0 || s > t || line[s] != u) continue;
                auto posPath = linePath(t, s, t, need);
                if (posPath.empty()) continue;

                vector<int> res;
                for (int pos : posPath) res.push_back(line[pos]);
                return res;
            }

            return vector<int>{};
        };

        vector<vector<int>> op1, op2;
        vector<vector<int>> cur = orig;

        for (int u = 0; u < n; u++) {
            for (int v = u + 1; v < n; v++) {
                if (dist[u][v] == 2 && !cur[u][v]) {
                    int mid = -1;
                    for (int x = 0; x < n; x++) {
                        if (dist[u][x] == 1 && dist[v][x] == 1) mid = x;
                    }
                    op1.push_back({u, mid, v});
                    cur[u][v] = cur[v][u] = 1;
                }
            }
        }

        for (int u = 0; u < n; u++) {
            for (int v = u + 1; v < n; v++) {
                if (!cur[u][v]) {
                    auto p = makePath(u, v, L);
                    op2.push_back(p);
                    cur[u][v] = cur[v][u] = 1;
                }
            }
        }

        auto printPath = [&](const vector<int>& p) {
            for (int i = 0; i < (int)p.size(); i++) {
                if (i) cout << ' ';
                cout << p[i] + 1;
            }
            cout << '\n';
        };

        cout << 2 << '\n';
        cout << 3 << '\n';
        cout << op1.size() << '\n';
        for (auto &p : op1) printPath(p);
        cout << L + 1 << '\n';
        cout << op2.size() << '\n';
        for (auto &p : op2) printPath(p);
    }
}