#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define cout cerr
struct DSU {
int n; vector<int> par, sz, U, P;
DSU(int n = 0) : n(n), par(n, -1), sz(n, 1) {}
int find(int v) {return par[v] == -1 ? v :find(par[v]);}
void unite(int a, int b) {
a =find(a); b = find(b);
if (a != b) {
if (sz[a] < sz[b]) swap(a, b);
U.push_back(b); P.push_back(par[b]);
par[b] = a; sz[a] += sz[b];
}
}
void rollback() {
if (U.empty()) return;
sz[par[U.back()]] -= sz[U.back()];
par[U.back()] = P.back();
U.pop_back(); P.pop_back();
}
};
vi find_roads(int n, vi u, vi v) {
int m = u.size();
deque<int> edges, cur; vi isbridge(m, 0);
for (int i = 0; i < m; i++) {
auto dsu = DSU(n);
for (int j = 0; j < m; j++) {
if (i == j) continue;
dsu.unite(u[j], v[j]);
}
if (dsu.sz[dsu.find(0)] != n) edges.push_back(i), isbridge[i] = 1;
}
auto dsu = DSU(n);
vi not_span_edge(m, 0);
vi mc; // hammer;
auto add = [&](int x) {
if (x<m) {
edges.push_back(x);
}
dsu = DSU(n); mc.clear();
for (auto e : edges) dsu.unite(u[e], v[e]), mc.push_back(e);
for (int i = 0; i < m; i++) {
if (dsu.find(u[i]) == dsu.find(v[i])) continue;
dsu.unite(u[i], v[i]); mc.push_back(i);
}
};
add(m);
bitset<125'000> avail; for (int i = 0; i < m; i++) avail[i] = 1;
while (edges.size() < n-1) {
int cnt = count_common_roads(mc);
int x = mc.back(); mc.pop_back();
dsu.rollback();
int best = x, bc = cnt;
for (int i = avail._Find_first(); i < m; i = avail._Find_next(i)) {
if (dsu.find(u[i]) == dsu.find(v[i])) continue;
dsu.unite(u[i], v[i]); mc.push_back(i);
int c2 = count_common_roads(mc);
dsu.rollback(); mc.pop_back();
if (c2 > bc) {best = i, bc = c2; break;}
else if (c2 < bc) avail[i] = 0;
}
if (best != x) avail[x] = 0;
add(best);
}
vi r; for (auto &e : edges) r.push_back(e);
return r;
}
