#define _GLIBCXX_DEBUG

#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(234);

struct DSU {
    int n;
    vector<int> t;

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

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;

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;
        }
        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);
    dfs0(0, 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];
        dfs1(u, rs);
    }
    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> solve_slow() {
    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});
    }
    int cnt = m;
    while (cnt > n - 1) {
        vector<int> c;
        find_cycle(c);
        reveal_cycle(c);
        for (auto j : c) {
            if (tp[j] == 0) {
                delete_edge_from_g(j);
                cnt -= 1;
            }
        }
    }
    vector<int> rs;
    for (int v = 0; v < n; v += 1) {
        for (auto [to, i] : g[v]) {
            if (to < v) {
                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;
}

/usr/bin/ld: /tmp/ccIKZscY.o: in function `main':
implementer.cpp:(.text.startup+0x2ed): undefined reference to `find_roads(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: /tmp/ccANbox1.o: in function `reveal_cycle(std::__debug::vector<int, std::allocator<int> >&)':
answer.code:(.text+0x42c6): undefined reference to `count_common_roads(std::__debug::vector<int, std::allocator<int> > const&)'
collect2: error: ld returned 1 exit status