#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();
}
};
int timer = 0;
vi X, Y;
void dfs(int u, int p, vvi &G, vi &tin, vi &low, deque<int> &bridges) {
tin[u] = low[u] = timer++;
for (auto e : G[u]) {
int v = X[e] == u ? Y[e] : X[e];
if (v == p) continue;
if (tin[v] != -1) {
low[u] = min(low[u], tin[v]);
continue;
}
dfs(v, u, G, tin, low, bridges);
if (low[v] > tin[u]) bridges.push_back(e);
low[u] = min(low[u], low[v]);
}
}
vi find_roads(int n, vi u, vi v) {
int m = u.size();
X = u; Y = v;
vvi G(n); for (int i = 0; i < m; i++) G[u[i]].push_back(i), G[v[i]].push_back(i);
deque<int> edges; vi tin(n, -1), low(n, -1);
dfs(0, 0, G, tin, low, edges);
auto dsu = DSU(n);
vi not_span_edge(m, 0);
vi mc; // hammer;
bitset<125'000> avail; for (int i = 0; i < m; i++) avail[i] = 1;
auto add = [&](int x) {
if (x<m && avail[x]) {
edges.push_back(x);
avail[x] = 0;
}
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);
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;
vi eq;
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;
for (auto &v : eq) avail[v] = 0;
eq.clear();
}
else if (c2 == bc) eq.push_back(i);
else if (c2 < bc) avail[i] = 0;
}
if (best != x) avail[x] = 0;
else for (auto v : eq) add(v);
add(best);
}
vi r; for (auto &e : edges) r.push_back(e);
return r;
}
