#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
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);
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) {
int cnt = count_common_roads(vi(cur.begin(), cur.end()));
int x = cur.back(); cur.pop_back();
dsu.rollback();
bool good = false;
for (int i = 0; i < m; i++) {
if (dsu.find(u[i]) == dsu.find(v[i])) continue;
// if (!not_span_edge[i]) continue;
dsu.unite(u[i], v[i]); cur.push_back(i);
int c2 = count_common_roads(vi(cur.begin(), cur.end()));
if (cnt == c2) {
good = false;
not_span_edge[i] = 1;
dsu.rollback();
cur.pop_back();
} else if (cnt > c2) {
good = true;
not_span_edge[i] = 1;
break;
} else if (c2 > cnt) {
add(i);
break;
}
}
if (!good) not_span_edge[x] = 1;
else add(x);
}
vi r; for (auto &e : edges) r.push_back(e);
return r;
}
