CF1883G WA

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifdef __DEBUG__
#include "dbg.h"
#else
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;
using a3b = array<bool, 3>;

a3b dfs(int u, int fa, const map<pii, int> &e, const vector<vector<int>> &g, vector<a3b> &c)
{
    a3b ret = {true, false, false};
    int need0 = 0, need1 = 0, need2 = 0, ssize = 0;
    for (auto v : g[u]) {
        if (v == fa)
            continue;
        auto sub = dfs(v, u, e, g, c);
        need0 += sub[2] == true;
        need1 += sub[1] == true;
        need2 += sub[0] == true;
        ssize++;
    }
    ret[0] = ssize == need0;
    ret[1] = ssize - 1 == need0 && need2 == 1;
    ret[2] = (ssize - 2 == need0 && need2 == 2) || (ssize - 1 == need0 && need1 == 1);
    return c[u] = ret;
}

void process(int u, int fa, int given, const map<pii, int> &e, const vector<vector<int>> &g, const vector<a3b> &c,
             vi &cut)
{
    if (given == 0) {
        int a = min(fa, u), b = max(fa, u);
        if (e.count({a, b}))
            cut.push_back(e.at({a, b}));
        vi n0, n1, n2;
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            if (c[v][0])
                n2.push_back(v);
            if (c[v][1])
                n1.push_back(v);
            if (c[v][2])
                n0.push_back(v);
        }
        for (auto v : n0)
            process(v, u, 0, e, g, c, cut);
        if (n2.size() == 2) {
            for (auto v : n2)
                process(v, u, 1, e, g, c, cut);
        } else {
            for (auto v : n1)
                process(v, u, 1, e, g, c, cut);
        }
    } else if (given == 2)
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            process(v, u, 0, e, g, c, cut);
        }
    else {
        // given == 1
        int choosen = -1;
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            if (c[v][1] == true && c[v][2] == false) {
                process(v, u, 2, e, g, c, cut);
            } else {
                process(v, u, 0, e, g, c, cut);
            }
        }
    }
}

int main(int argc, char **argv)
{
    int t, n;
    cin >> t;
    while (t--) {
        dbg(t);
        cin >> n;
        vector<vector<int>> g(n + 1);
        vector<a3b> c(n + 1);
        vi cut;
        map<pii, int> e;
        for (int i = 1; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            e[{min(x, y), max(x, y)}] = i;
            g[x].push_back(y), g[y].push_back(x);
        }
        if (n % 3) {
            dbg(n % 3);
            cout << -1 << endl;
            continue;
        }
        auto ans = dfs(1, -1, e, g, c);
        if (ans[2] == false) {
            dbg(ans[2]);
            cout << -1 << endl;
            continue;
        }
        process(1, -1, 0, e, g, c, cut);
        if (cut.size()) {
            cout << cut.size() << endl;
            for (auto c : cut)
                cout << c << ' ';
        }
        cout << endl;
    }
    return 0;
};