#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
static int status[300005];
static vector<pair<int, int>> adj[505];
static int depth[505], parent_n[505], parent_e[505];
static bool vis[505];
static vector<int> tree_edges;
static bool is_te[300005];
struct DSU {
vector<int> p;
DSU(int n) { p.resize(n); iota(p.begin(), p.end(), 0); }
int find(int i) { return (p[i] == i) ? i : (p[i] = find(p[i])); }
bool unite(int i, int j) {
int root_i = find(i), root_j = find(j);
if (root_i != root_j) { p[root_i] = root_j; return true; }
return false;
}
};
void dfs(int u, int p, int d) {
vis[u] = true;
depth[u] = d;
for (auto &edge : adj[u]) {
int v = edge.first, id = edge.second;
if (v == p) continue;
if (!vis[v]) {
parent_n[v] = u;
parent_e[v] = id;
tree_edges.push_back(id);
is_te[id] = true;
dfs(v, u, d + 1);
}
}
}
void identify_tree(int n, int m, const vector<int>& u, const vector<int>& v) {
for (int i = 0; i < m; i++) {
if (is_te[i] || status[i] != -1) continue;
vector<int> cycle;
int x = u[i], y = v[i];
while (x != y) {
if (depth[x] > depth[y]) { cycle.push_back(parent_e[x]); x = parent_n[x]; }
else { cycle.push_back(parent_e[y]); y = parent_n[y]; }
}
cycle.push_back(i);
int ref = -1;
for (int e : cycle) if (status[e] != -1) { ref = e; break; }
int sres = 0;
if (ref != -1) sres = status[ref];
vector<int> results(cycle.size(), -1);
int mx = -1, mn = 1e9;
for (int j = 0; j < (int)cycle.size(); j++) {
int cur = cycle[j];
if (ref != -1 && status[cur] != -1 && cur != ref) continue;
vector<int> q;
for (int te : tree_edges) {
bool in_c = false;
for (int ce : cycle) if (ce == te) in_c = true;
if (!in_c) q.push_back(te);
}
for (int k = 0; k < (int)cycle.size(); k++) {
if (k != j && cycle[k] != i) q.push_back(cycle[k]);
}
if (j != (int)cycle.size() - 1) q.push_back(i);
results[j] = count_common_roads(q);
mx = max(mx, results[j]);
mn = min(mn, results[j]);
}
for (int j = 0; j < (int)cycle.size(); j++) {
if (results[j] == -1) continue;
if (mx == mn) status[cycle[j]] = 0;
else status[cycle[j]] = (results[j] == mn ? 1 : 0);
}
}
for (int te : tree_edges) if (status[te] == -1) status[te] = 1;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
tree_edges.clear();
for (int i = 0; i < n; i++) { adj[i].clear(); vis[i] = false; }
for (int i = 0; i < m; i++) { status[i] = -1; is_te[i] = false; adj[u[i]].push_back({v[i], i}); adj[v[i]].push_back({u[i], i}); }
dfs(0, -1, 0);
identify_tree(n, m, u, v);
for (int i = 0; i < n; i++) {
vector<int> cand;
for (auto &edge : adj[i]) {
int id = edge.second;
int other = (u[id] == i ? v[id] : u[id]);
if (i < other && status[id] == -1) cand.push_back(id);
}
auto solve = [&](auto self, vector<int> c) -> void {
if (c.empty()) return;
DSU dsu(n);
for (int id : c) dsu.unite(u[id], v[id]);
vector<int> q = c;
int ts = 0;
for (int te : tree_edges) if (dsu.unite(u[te], v[te])) { q.push_back(te); if (status[te] == 1) ts++; }
int found = count_common_roads(q) - ts;
if (found == 0) { for (int id : c) status[id] = 0; }
else if (found == (int)c.size()) { for (int id : c) status[id] = 1; }
else {
int mid = c.size() / 2;
self(self, vector<int>(c.begin(), c.begin() + mid));
self(self, vector<int>(c.begin() + mid, c.end()));
}
};
solve(solve, cand);
}
vector<int> res;
for (int i = 0; i < m; i++) if (status[i] == 1) res.push_back(i);
return res;
}
