#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) {
// 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 cycle(int e) {
int u = par[x[e]] == e ? y[e] : x[e]; int v = u == x[e] ? y[e] : x[e];
vi ans(1, e);
int cur = v;
while (is_tree_edge(back[cur])) ans.push_back(back[cur]), cur = x[back[cur]]^y[back[cur]]^cur;
int be = back[cur];
int anc = tin[x[be]] < tin[y[be]] ? x[be] : y[be];
vi to_anc; cur = u;
while (cur != anc) to_anc.push_back(par[cur]), cur = x[par[cur]]^y[par[cur]]^cur;
ans.push_back(be);
reverse(to_anc.begin(), to_anc.end());
for (auto e: to_anc) ans.push_back(e);
return ans;
}
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;
}
