1833G - Ksyusha and Chinchilla - CodeForces Solution

// trust the process
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) begin(v), end(v)
#define ff first
#define ss second
#define sz(x) ((int)x.size())

const char nl = '\n';
const int inf = 1e9 + 9;
const long long INF = 1e18 + 18;
const int N = 2e5 + 5;

vector<int> g[N];
vector<int> ans;
map<int, map<int, int> > mp;

int dfs(int u, int p) {
    int cur = 1;
    for (int v : g[u]) {
        if (v == p) continue;
        cur += dfs(v, u);
    }
    if (cur == 3) {
        ans.push_back(mp[u][p]);
        return 0;
    }
    return cur;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;

        mp.clear();
        mp.insert({0, {{-1, -1}}});
        for (int i = 0; i < n; i++) {
            g[i].clear();
        }

        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            g[u].push_back(v);
            g[v].push_back(u);
            mp[u][v] = mp[v][u] = i + 1;
        }
        
        if (n % 3) {
            cout << "-1\n";
            continue;
        }

        ans.clear();
        dfs(0, -1);
        if ((int)ans.size() != n / 3) {
            cout << "-1\n";
            continue;
        }

        cout << n / 3 - 1 << nl;
        for (int i = 0; i < (int)ans.size() - 1; i++) {
            cout << ans[i] << " ";
        }
        cout << nl;
    }
}