#include <bits/stdc++.h>
#include "simurgh.h"
template <class T>
using Vec = std::vector<T>;
Vec<int> find_roads(int n, Vec<int> U, Vec<int> V) {
Vec<Vec<std::pair<int, int>>> graph(n);
const int m = (int) U.size();
for (int i = 0; i < m; ++i) {
graph[U[i]].emplace_back(V[i], i);
graph[V[i]].emplace_back(U[i], i);
}
Vec<char> visited(n);
Vec<int> depth(n), pedge(n, -1);
Vec<int> edges;
std::set<int> tree;
auto dfs = [&](auto dfs, const int u) -> void {
visited[u] = true;
for (const auto [v, e]: graph[u]) {
if (visited[v]) {
if (depth[u] + 1 < depth[v]) {
edges.push_back(e);
}
}
else {
depth[v] = depth[u] + 1;
pedge[v] = e;
tree.insert(e);
dfs(dfs, v);
}
}
};
dfs(dfs, 0);
for (int i = 0; i < m; ++i) {
if (depth[U[i]] > depth[V[i]]) {
std::swap(U[i], V[i]);
}
}
Vec<char> state(m, 2);
const auto ask = [&] {
return count_common_roads(Vec<int>(tree.begin(), tree.end()));
};
const auto exchange = [&](const int f, const int e) {
tree.erase(f);
tree.insert(e);
const auto ret = ask();
tree.insert(f);
tree.erase(e);
return ret;
};
const auto base = ask();
for (const auto e: edges) {
int X = U[e], Y = V[e];
Vec<int> ok, ng;
while (Y != X) {
const auto f = pedge[Y];
(state[f] == 2 ? ok : ng).push_back(f);
Y = U[f];
}
Vec<int> same, differ;
for (const auto f: ok) {
const auto tmp = exchange(f, e);
if (tmp < base) {
state[e] = 0;
differ.push_back(f);
}
else if (tmp > base) {
state[e] = 1;
differ.push_back(f);
}
else {
same.push_back(f);
}
}
if (state[e] == 2) {
if (ng.empty()) {
state[e] = 0;
}
else {
const auto f = ng.front();
if (base == exchange(f, e)) {
state[e] = state[f];
}
else {
state[e] = 1 - state[f];
}
}
}
for (const auto f: same) {
state[f] = state[e];
}
for (const auto f: differ) {
state[f] = 1 - state[e];
}
}
Vec<int> ret;
for (int i = 0; i < m; ++i) {
if (state[i] != 0) {
ret.push_back(i);
}
}
return ret;
}
