#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#endif

#include <bits/stdc++.h>

#include "simurgh.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

const ll inf = 1e18;
mt19937 rnd(543);

struct DSU {
    int n;
    vector<int> t;
    int cmps = 0;

    void build(int _n) {
        n = _n;
        t.resize(n);
        for (int i = 0; i < n; i += 1) {
            t[i] = i;
        }
        cmps = n;
    }

    int get(int v) {
        if (t[v] == v) {
            return v;
        }
        return (t[v] = get(t[v]));
    }

    void merge(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) {
            return;
        }
        cmps -= 1;
        t[a] = b;
    }

    int get_cmps() {
        return cmps;
    }
};

struct edge {
    int to, i;
};

bool operator==(const edge &a, const edge &b) {
    return a.to == b.to && a.i == b.i;
}

int n, m;
vector<pair<int, int>> edgs;
vector<int> tp;
vector<vector<edge>> g;
vector<int> usd;
vector<int> h;
DSU dsu;
vector<int> bbr;
vector<int> cool;

bool dfs0(int v, int mh, int pri, vector<int> &stck, vector<int> &cycle) {
    h[v] = mh;
    usd[v] = 1;
    for (auto [to, i] : g[v]) {
        if (pri == i) {
            continue;
        }
        if (usd[to] == 1) {
            int dst = mh - h[to];
            cycle = vector<int>(stck.end() - dst, stck.end());
            cycle.push_back(i);
            return true;
        }
    }
    for (auto [to, i] : g[v]) {
        if (usd[to] == 0 && cool[i]) {
            stck.push_back(i);
            int x = dfs0(to, mh + 1, i, stck, cycle);
            stck.pop_back();
            if (x) {
                return true;
            }
        }
    }
    for (auto [to, i] : g[v]) {
        if (usd[to] == 0 && tp[i] != -1) {
            stck.push_back(i);
            int x = dfs0(to, mh + 1, i, stck, cycle);
            stck.pop_back();
            if (x) {
                return true;
            }
        }
    }
    for (auto [to, i] : g[v]) {
        if (usd[to] == 0) {
            stck.push_back(i);
            int x = dfs0(to, mh + 1, i, stck, cycle);
            stck.pop_back();
            if (x) {
                return true;
            }
        }
    }
    usd[v] = 2;
    return false;
}

void find_cycle(vector<int> &cycle) {
    usd.assign(n, 0);
    h.resize(n);
    vector<int> stck;
    stck.reserve(n);
    int v0 = -1;
    while (v0 == -1) {
        int i = bbr[rnd() % (n - 1)];
        if (tp[i] == -1) {
            auto [u, v] = edgs[i];
            if (rnd() % 2) {
                v0 = u;
            } else {
                v0 = v;
            }
        }
    }
    dfs0(v0, 0, -1, stck, cycle);
}

void dfs1(int v, vector<int> &rs) {
    usd[v] = 1;
    for (auto [to, i] : g[v]) {
        if (!usd[to]) {
            rs.push_back(i);
            dfs1(to, rs);
        }
    }
}

vector<int> add_edgs(vector<int> &c) {
    auto rs = c;
    usd.assign(n, 0);
    for (auto i : c) {
        auto [u, v] = edgs[i];
        usd[u] = 1;
        usd[v] = 1;
    }
    for (auto i : c) {
        auto [u, v] = edgs[i];
        if (usd[u] == 1) {
            dfs1(u, rs);
            usd[u] = 2;
        }
        if (usd[v] == 1) {
            dfs1(v, rs);
            usd[v] = 2;
        }
    }
    return rs;
}

void reveal_cycle(vector<int> &c) {
    auto f = add_edgs(c);
    int sz = (int)c.size();
    vector<int> p(sz, -1);
    int mx = 0;
    for (int i = 0; i < sz; i += 1) {
        int j = c[i];
        if (tp[j] == -1) {
            auto nf = f;
            nf.erase(nf.begin() + i);
            p[i] = count_common_roads(nf);
            mx = max(mx, p[i]);
        }
    }
    for (int i = 0; i < sz; i += 1) {
        int j = c[i];
        if (tp[j] == -1) {
            if (p[i] == mx) {
                tp[j] = 0;
            } else {
                tp[j] = 1;
            }
        }
    }
}

void erase(vector<edge> &t, const edge &x) {
    for (int i = 0; i < (int)t.size(); i += 1) {
        if (t[i] == x) {
            t.erase(t.begin() + i);
            break;
        }
    }
}

void delete_edge_from_g(int i) {
    auto [u, v] = edgs[i];
    erase(g[u], edge{v, i});
    erase(g[v], edge{u, i});
}

vector<int> tr;

int count_gd_edgs(vector<int> p) {
    if (p.empty()) {
        return 0;
    }
    DSU mdsu;
    mdsu.build(n);
    for (auto i : p) {
        auto [u, v] = edgs[i];
        mdsu.merge(u, v);
    }
    auto f = p;
    int rs = 0;
    for (auto i : tr) {
        auto [u, v] = edgs[i];
        if (mdsu.get(u) != mdsu.get(v)) {
            mdsu.merge(u, v);
            f.push_back(i);
            if (tp[i] == 1) {
                rs -= 1;
            }
        }
    }
    rs += count_common_roads(f);
    return rs;
}

void reveal_edgs(int tl, int tr, vector<int> p, int x) {
    if (x == 0) {
        for (int j = tl; j <= tr; j += 1) {
            int i = p[j];
            tp[i] = 0;
        }
        return;
    }
    if (x == tr - tl + 1) {
        for (int j = tl; j <= tr; j += 1) {
            int i = p[j];
            tp[i] = 1;
        }
        return;
    }
    int tm = (tl + tr) / 2;
    int xl = count_gd_edgs(vector<int>(p.begin() + tl, p.begin() + tm + 1));
    int xr = x - xl;
    reveal_edgs(tl, tm, p, xl);
    reveal_edgs(tm + 1, tr, p, xr);
}

void reveal_edgs(vector<int> p) {
    int x = count_gd_edgs(p);
    reveal_edgs(0, (int)p.size() - 1, p, x);
}

int tinc;
vector<int> tin;
vector<int> fup;

void dfs3(int v, int pi) {
    usd[v] = 1;
    fup[v] = tin[v] = tinc++;
    for (auto [to, i] : g[v]) {
        if (i == pi) {
            continue;
        }
        if (!usd[to]) {
            dfs3(to, i);
            if (fup[to] > tin[v]) {
                tp[i] = 1;
            }
            fup[v] = min(fup[to], fup[v]);
        } else {
            fup[v] = min(fup[to], fup[v]);
        }
    }
    usd[v] = 2;
}

void fuck_bridges() {
    tin.resize(n);
    fup.resize(n);
    usd.assign(n, false);
    tinc = 0;
    dfs3(0, -1);
    for (int i = 0; i < m; i += 1) {
        if (tp[i] != -1) {
            auto [u, v] = edgs[i];
            dsu.merge(u, v);
        }
    }
}

vector<int> solve_slow() {
    if (m == n - 1) {
        vector<int> rs(n - 1);
        for (int i = 0; i < n - 1; i += 1) {
            rs[i] = i;
        }
        return rs;
    }
    DSU mdsu;
    mdsu.build(n);
    bbr.clear();
    vector<int> prm(m);
    for (int i = 0; i < m; i += 1) {
        prm[i] = i;
    }
    shuffle(all(prm), rnd);
    cool.assign(m, false);
    for (auto i : prm) {
        auto [u, v] = edgs[i];
        if (mdsu.get(u) != mdsu.get(v)) {
            mdsu.merge(u, v);
            bbr.push_back(i);
            cool[i] = true;
        }
    }
    dsu.build(n);
    tp.assign(m, -1);
    g.assign(n, vector<edge>());
    for (int i = 0; i < m; i += 1) {
        auto [u, v] = edgs[i];
        g[u].push_back(edge{v, i});
        g[v].push_back(edge{u, i});
    }
    fuck_bridges();
    int cnt = m;
    int good_count = 0;
    while (dsu.get_cmps() > 1 && cnt > n - 1 && good_count < n - 1) {
        vector<int> c;
        find_cycle(c);
        reveal_cycle(c);
        for (auto j : c) {
            auto [u, v] = edgs[j];
            dsu.merge(u, v);
            if (tp[j] == 0) {
                delete_edge_from_g(j);
                // cnt -= 1;
            }
        }
        fuck_bridges();
        good_count = 0;
        for (int i = 0; i < m; i += 1) {
            if (tp[i] == 1) {
                good_count += 1;
            }
        }
    }
    if (cnt == n - 1) {
        for (int i = 0; i < m; i += 1) {
            if (tp[i] == -1) {
                tp[i] = 1;
            }
        }
    }
    tr.clear();
    for (int i = 0; i < m; i += 1) {
        if (tp[i] != -1) {
            tr.push_back(i);
        }
    }
    while (good_count < n - 1) {
        vector<int> p;
        DSU mdsu;
        mdsu.build(n);
        vector<int> prm(m);
        for (int i = 0; i < m; i += 1) {
            prm[i] = i;
        }
        shuffle(all(prm), rnd);
        for (auto i : prm) {
            if (tp[i] == -1) {
                auto [u, v] = edgs[i];
                if (mdsu.get(u) != mdsu.get(v)) {
                    mdsu.merge(u, v);
                    p.push_back(i);
                }
            }
        }
        if (p.empty()) {
            break;
        }
        reveal_edgs(p);
        good_count = 0;
        for (int i = 0; i < m; i += 1) {
            if (tp[i] == 1) {
                good_count += 1;
            }
        }
    }
    vector<int> rs;
    for (int i = 0; i < m; i += 1) {
        if (tp[i] == 1) {
            rs.push_back(i);
        }
    }
    return rs;
}

vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
    n = _n;
    m = _u.size();
    edgs.resize(m);
    for (int i = 0; i < m; i += 1) {
        edgs[i] = make_pair(_u[i], _v[i]);
    }
    auto rs = solve_slow();
    return rs;
}