#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
DSU(int n = 0) {
p.resize(n);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int N, M;
vector<int> U, V;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
vector<bool> is_bridge;
int timer_dfs;
void dfs_bridge(int v, int pe) {
tin[v] = low[v] = timer_dfs++;
for (auto [to, id] : g[v]) {
if (id == pe) continue;
if (tin[to] != -1) {
low[v] = min(low[v], tin[to]);
} else {
dfs_bridge(to, id);
low[v] = min(low[v], low[to]);
if (low[to] > tin[v]) {
is_bridge[id] = true;
}
}
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
N = n;
U = u;
V = v;
M = (int)U.size();
g.assign(N, {});
for (int i = 0; i < M; i++) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
tin.assign(N, -1);
low.assign(N, 0);
is_bridge.assign(M, false);
timer_dfs = 0;
dfs_bridge(0, -1);
vector<bool> royal(M, false);
for (int i = 0; i < M; i++) {
if (is_bridge[i]) royal[i] = true;
}
vector<int> comp(N, -1);
vector<vector<int>> comp_vertices;
for (int s = 0; s < N; s++) {
if (comp[s] != -1) continue;
int cid = (int)comp_vertices.size();
comp_vertices.push_back({});
queue<int> q;
q.push(s);
comp[s] = cid;
while (!q.empty()) {
int x = q.front();
q.pop();
comp_vertices[cid].push_back(x);
for (auto [to, id] : g[x]) {
if (is_bridge[id]) continue;
if (comp[to] == -1) {
comp[to] = cid;
q.push(to);
}
}
}
}
int C = (int)comp_vertices.size();
vector<vector<int>> comp_edges(C);
for (int i = 0; i < M; i++) {
if (!is_bridge[i]) {
comp_edges[comp[U[i]]].push_back(i);
}
}
vector<vector<int>> comp_tree_edges(C);
vector<int> base_tree;
for (int i = 0; i < M; i++) {
if (is_bridge[i]) {
base_tree.push_back(i);
}
}
for (int c = 0; c < C; c++) {
DSU dsu(N);
for (int id : comp_edges[c]) {
if (dsu.unite(U[id], V[id])) {
comp_tree_edges[c].push_back(id);
base_tree.push_back(id);
}
}
}
vector<int> pos_in_base(M, -1);
for (int i = 0; i < (int)base_tree.size(); i++) {
pos_in_base[base_tree[i]] = i;
}
int base_ans = count_common_roads(base_tree);
for (int c = 0; c < C; c++) {
if ((int)comp_vertices[c].size() <= 1) continue;
vector<vector<pair<int, int>>> tree(N);
vector<bool> in_tree(M, false);
for (int id : comp_tree_edges[c]) {
in_tree[id] = true;
tree[U[id]].push_back({V[id], id});
tree[V[id]].push_back({U[id], id});
}
vector<int> parent(N, -1), parent_edge(N, -1), tin2(N, -1), tout2(N, -1);
int timer2 = 0;
function<void(int, int)> dfs_tree = [&](int x, int p) {
tin2[x] = timer2++;
for (auto [to, id] : tree[x]) {
if (to == p) continue;
parent[to] = x;
parent_edge[to] = id;
dfs_tree(to, x);
}
tout2[x] = timer2;
};
dfs_tree(comp_vertices[c][0], -1);
for (int e1 : comp_tree_edges[c]) {
int a = U[e1], b = V[e1];
int child;
if (parent[a] == b) child = a;
else child = b;
auto inside = [&](int x) {
return tin2[child] <= tin2[x] && tin2[x] < tout2[child];
};
map<int, vector<int>> by_ans;
by_ans[base_ans].push_back(e1);
for (int e2 : comp_edges[c]) {
if (!inside(U[e2]) == !inside(V[e2])) continue;
if (e2 == e1) continue;
vector<int> query_tree = base_tree;
query_tree[pos_in_base[e1]] = e2;
int ans = count_common_roads(query_tree);
by_ans[ans].push_back(e2);
}
if ((int)by_ans.size() == 1) {
for (auto &[val, edges] : by_ans) {
for (int id : edges) {
royal[id] = true;
}
}
} else {
auto it = by_ans.rbegin();
for (int id : it->second) {
royal[id] = true;
}
}
}
}
vector<int> ans;
for (int i = 0; i < M; i++) {
if (royal[i]) ans.push_back(i);
}
return ans;
}
