#include "simurgh.h"

// #include <bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <random>

struct DSU {
    std::vector<int> prv;

    DSU(int n) {
        clear(n);
    }

    void clear(int n) {
        prv.assign(n, -1);
    }

    int get(int i) {
        return prv[i] == -1 ? i : prv[i] = get(prv[i]);
    }

    void merge(int u, int v) {
        u = get(u);
        v = get(v);
        assert(u != v);
        prv[u] = v;
    }
};

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    static std::mt19937 rnd;

    int m = u.size();
    std::vector<std::pair<int, int>> edg(m);
    for (int i = 0; i < m; i++) {
        edg[i] = {u[i], v[i]};
    }

    std::vector<int> all(m);
    std::iota(all.begin(), all.end(), 0);
    std::shuffle(all.begin(), all.end(), rnd);

    std::vector<int> ans;
    DSU dsu(n);

    for (int i : all) {
        auto [u, v] = edg[i];
        if (dsu.get(u) != dsu.get(v)) {
            dsu.merge(u, v);
            ans.push_back(i);
        }
    }

    int cnt_rl = count_common_roads(ans);
    while (cnt_rl != n - 1) {
        std::shuffle(all.begin(), all.end(), rnd);

        auto ans2 = ans;
        std::shuffle(ans2.begin(), ans2.end(), rnd);
        ans2.pop_back();
        dsu.clear(n);

        for (int i : ans2) {
            auto [u, v] = edg[i];
            dsu.merge(u, v);
        }
        for (int i : all) {
            auto [u, v] = edg[i];
            if (dsu.get(u) != dsu.get(v)) {
                dsu.merge(u, v);
                ans2.push_back(i);
            }
        }

        int cnt_rl2 = count_common_roads(ans2);
        if (cnt_rl2 > cnt_rl) {
            ans = ans2;
            cnt_rl = cnt_rl2;
        }
    }
    return ans;
}