#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 x, int pe) {
tin[x] = low[x] = timer_dfs++;
for (auto [to, id] : g[x]) {
if (id == pe) continue;
if (tin[to] != -1) {
low[x] = min(low[x], tin[to]);
} else {
dfs_bridge(to, id);
low[x] = min(low[x], low[to]);
if (low[to] > tin[x]) {
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<int> known(M, -1);
for (int i = 0; i < M; i++) {
if (is_bridge[i]) known[i] = 1;
}
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);
map<pair<int, int>, int> swap_cache;
auto ask_swap = [&](int e1, int e2) {
pair<int, int> key = {e1, e2};
if (swap_cache.find(key) != swap_cache.end()) {
return swap_cache[key];
}
vector<int> q = base_tree;
q[pos_in_base[e1]] = e2;
return swap_cache[key] = count_common_roads(q);
};
auto set_known = [&](int id, int val) {
if (known[id] == -1) {
known[id] = val;
}
};
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), 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[to] = x;
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];
};
vector<int> crossing;
for (int e2 : comp_edges[c]) {
if (e2 == e1) continue;
if (inside(U[e2]) != inside(V[e2])) {
crossing.push_back(e2);
}
}
if (known[e1] != -1) {
for (int e2 : crossing) {
if (known[e2] != -1) continue;
int val = ask_swap(e1, e2);
int diff = val - base_ans;
set_known(e2, known[e1] + diff);
}
continue;
}
int known_edge = -1;
for (int e2 : crossing) {
if (known[e2] != -1) {
known_edge = e2;
break;
}
}
if (known_edge != -1) {
int val = ask_swap(e1, known_edge);
int diff = val - base_ans;
set_known(e1, known[known_edge] - diff);
for (int e2 : crossing) {
if (known[e2] != -1) continue;
int val2 = ask_swap(e1, e2);
int diff2 = val2 - base_ans;
set_known(e2, known[e1] + diff2);
}
} else {
map<int, vector<int>> by_ans;
by_ans[base_ans].push_back(e1);
for (int e2 : crossing) {
int val = ask_swap(e1, e2);
by_ans[val].push_back(e2);
}
int best = by_ans.rbegin()->first;
for (auto &[val, edges] : by_ans) {
for (int id : edges) {
set_known(id, val == best);
}
}
}
}
}
vector<int> ans;
for (int i = 0; i < M; i++) {
if (known[i] == 1) {
ans.push_back(i);
}
}
return ans;
}
