#include <bits/stdc++.h>
#include "simurgh.h"

using pii = std::pair<int, int>;
#define mkp(a, b) std::make_pair(a, b)

const int N = 5e2 + 10, M = N * N;

std::vector<int> Gold_Roads, Spanning_Tree;
int tot = 1, fir[N], nex[M], got[M], idx[M], Map[N][N], n;

inline void AddEdge(int u, int v, int I) {
    nex[++tot] = fir[u], fir[u] = tot, got[tot] = v, idx[tot] = I;
    nex[++tot] = fir[v], fir[v] = tot, got[tot] = u, idx[tot] = I;
}

int par[N], vis[N], dep[N], Vis[N], par_edge[N], TYPE[N], w[N], f[N], U[N], V[N], d[N];

inline void dfs(int u) {
    vis[u] = true;

    for (int i = fir[u]; i; i = nex[i])
        if (!vis[got[i]])
            Spanning_Tree.push_back(idx[i]), dfs(got[i]);
}

inline int find(int u) {
    return f[u] == u ? u : f[u] = find(f[u]);
}

inline int count(std::vector<int> E) {
    if (E.size() == n - 1)
        return count_common_roads(E);

    int s = 0;

    for (int i = 0; i < n; ++i)
        f[i] = i;

    for (int i = 0; i < E.size(); ++i) {
        int u = U[E[i]], v = V[E[i]];
        f[find(u)] = find(v);
    }

    for (auto i : Spanning_Tree) {
        int u = U[i], v = V[i];

        if (find(u) != find(v))
            f[find(u)] = find(v), s += TYPE[i], E.push_back(i);
    }

    return count_common_roads(E) - s;
}

inline std::vector<int> ring(std::vector<int> bas, int ban) {
    std::vector<int> res;

    for (auto dat : bas)
        if (dat != ban)
            res.push_back(dat);

    return res;
}

inline void solve(int u, int v, int edg_num) {
    int flg = 0, edg = 0;
    std::vector<int> query;
    memset(Vis, 0, sizeof(Vis));

    for (int U = u; U != v; U = par[U]) {
        Vis[par_edge[U]] = true;

        if (TYPE[par_edge[U]] != -1)
            flg = true, edg = par_edge[U];
    }

    if (flg) {
        std::vector<int> bas = Spanning_Tree;
        bas.push_back(edg_num);
        int sum = count(ring(bas, edg));

        for (int U = u; U != v; U = par[U]) {
            int e = par_edge[U];

            if (TYPE[e] == -1) {
                std::vector<int> query = ring(bas, e);
                int s = count(query);
                TYPE[e] = -TYPE[edg] + s - sum;
            }
        }
    } else {
        std::vector<int> bas = Spanning_Tree;
        int Min = count(bas);

        for (int U = u; U != v; U = par[U]) {
            int e = par_edge[U];
            std::vector<int> query = ring(bas, e);
            query.push_back(edg_num);
            w[U] = count(query), Min = std::min(Min, w[U]);
        }

        for (int U = u; U != v; U = par[U])
            TYPE[par_edge[U]] = 1 - w[U] + Min;
    }

    // for (int i = 0; i < 6; ++i) printf("%d ", TYPE[i]); puts("");
}

inline void dfs(int u, int fa) {
    par[u] = fa, vis[u] = true, dep[u] = dep[fa] + 1;

    for (int i = fir[u]; i; i = nex[i])
        if (got[i] != fa) {
            if (!vis[got[i]])
                par_edge[got[i]] = idx[i], dfs(got[i], u);
            else if (dep[u] > dep[got[i]])
                solve(u, got[i], idx[i]);
        }
}

inline int solve(int u, std::vector<int> vec) {
    if (vec.size() == 1)
        return vec[0];

    int mid = vec.size() / 2;
    std::vector<int> E;

    for (int i = 0; i < mid; ++i)
        E.push_back(Map[u][vec[i]]);

    if (count(E)) {
        std::vector<int> v;

        for (int i = 0; i < mid; ++i)
            v.push_back(vec[i]);

        return solve(u, v);
    } else {
        std::vector<int> v;

        for (int i = mid; i < vec.size(); ++i)
            v.push_back(vec[i]);

        return solve(u, v);
    }
}

inline int solve(int u) {
    std::vector<int> vec;

    for (int i = fir[u]; i; i = nex[i])
        if (TYPE[Map[u][got[i]]] == -1)
            vec.push_back(got[i]);

    return solve(u, vec);
}

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
    int m = U.size();
    n = N;

    for (int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        AddEdge(u, v, i);
        Map[u][v] = Map[v][u] = i;
        ::U[i] = u, ::V[i] = v;
    }

    memset(TYPE, -1, sizeof(TYPE));
    dfs(0), memset(vis, 0, sizeof(vis)), dfs(0, -1);

    for (auto i : Spanning_Tree)
        if (TYPE[i] == -1)
            TYPE[i] = 1;

    // for (int i = 0; i < m; ++i) printf("%d ", TYPE[i]); puts("");
    // std::cout << "Spanning_Tree.size() = " << Spanning_Tree.size() << std::endl;
    // for (int i: Spanning_Tree) printf("%d %d %d\n", U[i], V[i], TYPE[i]);
    for (int u = 0; u < n; ++u) {
        std::vector<int> E;

        for (int i = fir[u]; i; i = nex[i])
            E.push_back(idx[i]);

        d[u] = count(E);
    }

    for (auto i : Spanning_Tree)
        if (TYPE[i] == 1) {
            Gold_Roads.push_back(i), --d[U[i]], --d[V[i]];
        }

    for (int i = 0; i < n - 1; ++i) {
        for (int u = 0; u < n; ++u)
            if (d[u]) {
                int v = solve(u);
                Gold_Roads.push_back(Map[u][v]), --d[u], --d[v];
                TYPE[Map[u][v]] = 1;
                break;
            }
    }

    return Gold_Roads;
}