#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);
auto add = [&](int x) {
if (x<m) {
edges.push_back(x);
// cerr << "adding edge " << x << " as known\n";
}
dsu = DSU(n); cur.clear();
for (auto e : edges) dsu.unite(u[e], v[e]), cur.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]); cur.push_back(i);
}
};
add(m);
while (edges.size() < n-1) {
vi mc(cur.begin(), cur.end()); // hammer
int cnt = count_common_roads(mc);
int x = cur.back(); cur.pop_back(); mc.pop_back();
dsu.rollback();
int best = x, bc = cnt;
for (int i = 0; i < m; i++) {
if (dsu.find(u[i]) == dsu.find(v[i])) continue;
if (i == x) continue;
dsu.unite(u[i], v[i]); cur.push_back(i); mc.push_back(i);
int c2 = count_common_roads(mc);
dsu.rollback(); cur.pop_back(); mc.pop_back();
if (c2 > bc) best = i, bc = c2;
}
add(best);
}
vi r; for (auto &e : edges) r.push_back(e);
return r;
}
