#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;
DSU(int n = 0) : n(n), par(n, -1) {}
int find(int v) {return par[v] == -1 ? v :par[v] = find(par[v]);}
void unite(int a, int b) {if (find(a) != find(b)) par[find(b)] = find(a);}
};
int n, m, timer = 0;
vvi G; vi x, y, is_bridge, tin, low, par, back;
bool is_tree_edge(int e) {return par[x[e]] == e || par[y[e]] == e;}
void dfs(int u, int p) {
tin[u] = low[u] = timer++;
for (auto e : G[u]) {
if (e == p) continue;
int v = u^x[e]^y[e];
if (tin[v] != -1) {
if (tin[v] < low[u]) low[u] = tin[v], back[u] = e;
} else {
par[v] = e;
dfs(v, e);
if (low[v] > tin[u]) is_bridge[e] = 1;
if (low[v] < low[u]) back[u] = e, low[u] = low[v];
}
}
}
vi cycle(int e) {
if (!is_tree_edge(e)) {
int a = x[e], b = y[e];
int anc = tin[a] < tin[b] ? a : b;
int desc = anc == a ? b : a;
vi cyc = {e};
int cur = desc;
while (cur != anc) {
int pe = par[cur];
cyc.push_back(pe);
cur = x[pe]^y[pe]^cur;
}
return cyc;
}
int c = (par[x[e]] == e ? x[e] : y[e]);
int p = x[e]^y[e]^c;
vi down;
int cur = c;
while (true) {
int be = back[cur];
if (is_tree_edge(be)) {
int nxt = (par[x[be]] == be ? x[be] : y[be]);
down.push_back(be);
cur = nxt;
} else {
int z = cur;
int a = (tin[x[be]] < tin[y[be]] ? x[be] : y[be]);
vi up;
int u = p;
while (u != a) {
int pe = par[u];
up.push_back(pe);
u = u^x[pe]^y[pe];
}
reverse(up.begin(), up.end());
vi cyc;
cyc.push_back(e);
for (int x : down) cyc.push_back(x);
cyc.push_back(be);
for (int x : up) cyc.push_back(x);
return cyc;
}
}
}
vi find_roads(int N, vi U, vi V) {
n = N; m = U.size();
G.assign(n, vi()); x = U; y = V; is_bridge.assign(m, 0),
par.assign(n, -1), back.assign(n, -1); tin.assign(n, -1); low.assign(n, -1);
for (int i = 0; i < m; i++) G[x[i]].push_back(i), G[y[i]].push_back(i);
dfs(0, -1);
vi checked(m, 0), royal = is_bridge;
vi spanning_tree; for (int i = 1; i < n; i++) spanning_tree.push_back(par[i]);
auto test_subset = [&](vi s, bool sub = false) {
auto dsu = DSU(n);
for (auto e : s) dsu.unite(x[e], y[e]);
int expected = 0; for (auto e : spanning_tree) {
if (dsu.find(x[e]) == dsu.find(y[e])) continue;
dsu.unite(x[e], y[e]); s.push_back(e); if (royal[e]) expected++;
}
return count_common_roads(s) - (sub ? expected : 0);
};
for (auto i : spanning_tree) {
if (checked[i]) continue;
if (is_bridge[i]) continue;
vi c = cycle(i);
int found = -1; for (auto e : c) if (checked[e]) found = e;
if (found == -1) {
vi R(c.size()); int lo = INT_MAX, hi = INT_MIN;
for (int i = 0; i < c.size(); i++) {
vi c2; for (int j = 0; j < c.size(); j++) if (j != i) c2.push_back(c[j]);
R[i] = test_subset(c2); lo = min(lo, R[i]), hi = max(hi, R[i]);
}
for (int i = 0; i < c.size(); i++) {
checked[c[i]] = 1;
royal[c[i]] = R[i] != hi;
}
} else {
vi s1, s2;
for (auto e : c) {
if (e != found) s1.push_back(e);
if (e != i) s2.push_back(e);
}
int r1 = test_subset(s1), r2 = test_subset(s2);
if (r1 == r2) royal[i] = royal[found];
else if (r2 != r1) royal[i] = 1-royal[found];
checked[i] = checked[found] = 1;
}
}
for (int i = 0; i < m; i++) {
if (checked[i]) continue;
vi t(1, i); royal[i] = test_subset(t, true);
}
vi ans; for (int i = 0; i < m; i++) if (royal[i]) ans.push_back(i);
return ans;
}
