#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 512 * 512,M = 512;
int dat[N],dep[N],vis[N],m,w[N],p[N],pos[N];
bool in[N];
vector<int> tr;
vector<pair<int,int>>g[N];
void dfs(int v) {
    vis[v] = 1;
    for(auto [to,i]:g[v]) {
        if(vis[to]) continue;
        dep[to] = dep[v] + 1;
        tr.push_back(i);in[i] = 1;
        w[to] = i;p[to] = v;
        dfs(to);
    }
}
vector<int> upd(int i,int j) {
    vector<int> f = tr;
    f.erase(f.begin() + pos[i]);
    f.push_back(j);
    return f;
}
int P[N];
int get(int v) {
    if(P[v] == v) return v;
    return P[v] = get(P[v]);
}
bool merge(int a,int b) {
    a = get(a);
    b = get(b);
    if(a == b) return false;
    P[a] = b;
    return true;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    m = (int)v.size();
    for(int i = 0;i < (int)u.size();i++) {
        g[u[i]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }
    dfs(0);
    for(int i = 0;i < n - 1;i++) {
        pos[tr[i]] = i;
    }
    memset(dat,-1,sizeof(dat));
    int ct = count_common_roads(tr);
    for(int i = 0;i < m;i++) {
        if(in[i]) continue;
        if(dep[u[i]] > dep[v[i]]) {
            swap(u[i],v[i]);
        }
        int x = v[i];
        vector<int> t;
        while(x != u[i]) {
            t.push_back(w[x]);
            x = p[x];
        }
        sort(t.begin(),t.end(),[&](int x,int y) {
            return dat[x] < dat[y];
        });
        if(dat[t[0]] != -1) continue;
        int tp = -1;
        if(dat[t.back()] == -1) {
            vector<int> bf;
            for(int j:t) {
                vector<int> f = upd(j,i);
                int c = count_common_roads(f);
                if(c == ct + 1) {
                    tp = 1;
                    dat[j] = 0;
                } else if(c == ct - 1) {
                    tp = 0;
                    dat[j] = 1;
                } else {
                    bf.push_back(j);
                }
            }
            if(tp == -1) {
                tp = 0;
            }
            for(int j:bf) {
                dat[j] = tp;
            }
        } else {
            int c = count_common_roads(upd(t.back(),i));
            if(c == ct) {
                tp = dat[t.back()];
            } else if(c == ct - 1) {
                tp = 0;
            } else {
                tp = 1;
            }
            for(int j:t) {
                if(dat[j] != -1) continue;
                c = count_common_roads(upd(j,i));
                if(c == ct) {
                    dat[j] = tp;
                } else if(c == ct - 1) {
                    dat[j] = 1;
                } else {
                    dat[j] = 0;
                }
            }
        }
    }
    int left = (n - 1) - ct;
    for(int i = 0;i < n && left;i++) {
        int it = 0;
        auto check = [&](int l,int r)->bool {
            iota(P,P+n,0);
            vector<int> A;
            for(int j = l;j <= r;j++) {
                merge(i,g[i][j].first);
                A.push_back(g[i][j].second);
            }
            int _ = 0;
            for(int k:tr) {
                if(merge(u[k],v[k])) {
                    _ += dat[k];
                    A.push_back(k);
                }
            }
            _ = count_common_roads(A) - _;
            return (_ > 0);
        };
        for(int j = (int)g[i].size() - 1;j >= 0;--j) {
            if(in[g[i][j].second]) {
                g[i].erase(g[i].begin() + j);
            }
        }
        // cout << i << ' ' << (int)g[i].size() << '\n';
        while(it < (int)g[i].size()) {
            int l = it - 1,r = (int)g[i].size();
            while(r - l  > 1) {
                int mid = (l + r) >> 1;
                if(check(it,mid)) {
                    r = mid; 
                } else {
                    l = mid;
                }
            }
            if(r == (int)g[i].size()) break;
            dat[g[i][r].second] = 1;
            it = r + 1;
        }
    }
    tr.clear();
    for(int i = 0;i < m;++i) {
        if(dat[i] == 1) {
            tr.push_back(i);
        }
    }
    return tr;
}