#include "simurgh.h"

// #include <bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <iostream>
#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);
    std::vector<int> gold(m, -1);
    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);
            i = -1;
        }
    }
    all.erase(std::remove(all.begin(), all.end(), -1), all.end());
    int cnt_rl = count_common_roads(ans);
    std::shuffle(all.begin(), all.end(), rnd);

    int cnt_q = 1;
    while (!all.empty()) {
        int id = all.back();
        all.pop_back();

        std::shuffle(ans.begin(), ans.end(), rnd);

        // std::cerr << std::count_if(ans.begin(), ans.end(), [&](int i) { return gold[i] == 0; }) << "\n";

        std::vector<bool> used(n - 1);
        bool suc = false;
        for (int i = 0; i < n - 1; i++) {
            if (gold[ans[i]] == 1) {
                continue;
            }

            std::swap(ans[i], id);

            dsu.clear(n);
            bool fuck = false;
            for (int i : ans) {
                auto [u, v] = edg[i];
                if (dsu.get(u) == dsu.get(v)) {
                    fuck = true;
                    break;
                }
                dsu.merge(u, v);
            }

            if (!fuck) {
                int cnt2 = count_common_roads(ans);
                cnt_q++;

                std::swap(ans[i], id);

                if (cnt2 < cnt_rl) {
                    gold[ans[i]] = true;
                    gold[id] = false;
                    break;
                } else if (cnt2 > cnt_rl) {
                    cnt_rl = cnt2;

                    gold[ans[i]] = false;

                    gold[id] = true;
                    suc = true;
                    std::cerr << cnt2 << " " << cnt_q << "\n";

                    std::swap(ans[i], id);
                    break;
                } else {
                    assert(cnt_rl == cnt2);
                    if (gold[ans[i]] == 0) {
                        // std::cerr << "FFF\n";
                        gold[id] = 0;
                        break;
                    }

                    used[i] = true;
                    continue;
                }
            } else {
                std::swap(ans[i], id);
            }
        }
        if (!suc) {
            if (gold[id] == -1) {
                gold[id] = 0;
                // std::cerr << "cum: " << id << "\n";
            }
            if (gold[id] == 0) {
                for (int i = 0; i < n - 1; i++) {
                    if (used[i]) {
                        assert(gold[ans[i]] != 1);
                        gold[ans[i]] = 0;
                        // assert(get_cum(ans[i]) == gold[ans[i]]);
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            // assert(gold[i] == -1 || get_cum(i) == gold[i]);
        }
    }
    assert(cnt_rl == n - 1);
    return ans;
}