Maxflow GCD Coloring

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

using ll = long long;

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

struct InputEdge {
    int u, v;
    ll w;
};

struct Dinic {
    struct Edge {
        int to, rev;
        ll cap;
    };

    int n;
    vector<vector<Edge>> g;
    vector<int> level, it;

    Dinic(int n) : n(n), g(n), level(n), it(n) {}

    void addEdge(int v, int to, ll cap) {
        Edge a{to, (int)g[to].size(), cap};
        Edge b{v, (int)g[v].size(), 0};
        g[v].push_back(a);
        g[to].push_back(b);
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (const auto &e : g[v]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    ll dfs(int v, int t, ll pushed) {
        if (v == t) return pushed;
        for (int &i = it[v]; i < (int)g[v].size(); i++) {
            Edge &e = g[v][i];
            if (e.cap <= 0 || level[e.to] != level[v] + 1) continue;
            ll tr = dfs(e.to, t, min(pushed, e.cap));
            if (!tr) continue;
            e.cap -= tr;
            g[e.to][e.rev].cap += tr;
            return tr;
        }
        return 0;
    }

    ll maxflow(int s, int t) {
        ll flow = 0;
        const ll INF = (ll)4e18;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (true) {
                ll pushed = dfs(s, t, INF);
                if (!pushed) break;
                flow += pushed;
            }
        }
        return flow;
    }

    vector<int> reachable(int s) const {
        vector<int> seen(n, 0);
        queue<int> q;
        seen[s] = 1;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (const auto &e : g[v]) {
                if (e.cap > 0 && !seen[e.to]) {
                    seen[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
        return seen;
    }
};

pair<ll, vector<int>> mincut(int n, const vector<InputEdge> &edges, int s, int t) {
    Dinic dinic(n);
    for (auto e : edges) {
        dinic.addEdge(e.u, e.v, e.w);
        dinic.addEdge(e.v, e.u, e.w);
    }
    ll f = dinic.maxflow(s, t);
    return {f, dinic.reachable(s)};
}

ll gomoryHuGcd(int n, const vector<InputEdge> &edges) {
    if (n <= 1) return 0;

    vector<int> parent(n, 0);
    vector<ll> weight(n, 0);

    for (int s = 1; s < n; s++) {
        int t = parent[s];
        auto [f, cut] = mincut(n, edges, s, t);

        for (int i = s + 1; i < n; i++) {
            if (parent[i] == t && cut[i]) parent[i] = s;
        }

        if (cut[parent[t]]) {
            parent[s] = parent[t];
            parent[t] = s;
            weight[s] = weight[t];
            weight[t] = f;
        } else {
            weight[s] = f;
        }
    }

    ll g = 0;
    for (int i = 1; i < n; i++) g = std::gcd(g, weight[i]);
    return g;
}

vector<int> parityColoring(int n, const vector<InputEdge> &edges) {
    static const int B = 64;
    vector<bitset<B>> a(n);

    for (auto e : edges) {
        if ((e.w & 1) == 0) continue;
        int u = e.u, v = e.v;
        a[u].flip(v);
        a[v].flip(u);
        a[u].flip(u);
        a[v].flip(v);
        a[u].flip(n);
        a[v].flip(n);
    }

    vector<int> where(n, -1);
    int row = 0;
    for (int col = 0; col < n; col++) {
        int sel = -1;
        for (int i = row; i < n; i++) {
            if (a[i][col]) {
                sel = i;
                break;
            }
        }
        if (sel == -1) continue;
        swap(a[sel], a[row]);
        where[col] = row;

        for (int i = 0; i < n; i++) {
            if (i != row && a[i][col]) a[i] ^= a[row];
        }
        row++;
    }

    vector<int> x(n, 0);
    for (int col = 0; col < n; col++) {
        if (where[col] != -1) x[col] = (int)a[where[col]][n];
    }
    return x;
}

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

int main() {
    setIO();

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

        vector<InputEdge> edges(m);
        for (auto &e : edges) {
            cin >> e.u >> e.v >> e.w;
            --e.u;
            --e.v;
        }

        ll g = gomoryHuGcd(n, edges);

        if (g != 1) {
            vector<int> all(n);
            iota(all.begin(), all.end(), 0);
            cout << 1 << '\n';
            printGroup(all);
        } else {
            vector<int> color = parityColoring(n, edges);
            vector<int> zero, one;
            for (int i = 0; i < n; i++) {
                if (color[i]) one.push_back(i);
                else zero.push_back(i);
            }

            cout << 2 << '\n';
            printGroup(zero);
            printGroup(one);
        }
    }
}