#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 510;
const int M = 510 * 510 / 2;
int n, m;
int h[N];
pair<int, int> par[N];
bool visit[N];
bool tree_edge[M];
int visit_edge[M];
pair<int, int> e[M];
vector< pair<int, int> > G[N];
void dfs(int u) {
visit[u] = 1;
for (auto v : G[u]) {
if (visit[v.first]) continue;
tree_edge[v.second] = 1, h[v.first] = h[u] + 1;
par[v.first] = {u, v.second}, dfs(v.first);
}
}
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
n = _n, m = _u.size();
for (int i = 0; i < m; ++i) {
e[i] = {_u[i], _v[i]};
G[_u[i]].push_back({_v[i], i});
G[_v[i]].push_back({_u[i], i});
}
dfs(0);
vector<int> vec;
for (int i = 0; i < m; ++i) {
if (tree_edge[i]) vec.push_back(i);
}
int val = count_common_roads(vec);
for (int i = 0; i < m; ++i) {
if (h[e[i].first] > h[e[i].second]) swap(e[i].first, e[i].second);
if (tree_edge[i]) continue;
int cur = e[i].second;
vector<int> buf;
while (cur != e[i].first) {
buf.push_back(par[cur].second), cur = par[cur].first;
}
int id = -1;
for (auto j : buf) {
if (visit_edge[j]) id = j;
}
if (id == -1) {
for (auto j : buf) {
vector<int> ask = vec;
for (auto &k : ask) if (k == j) k = i;
int tmp = count_common_roads(ask);
if (tmp != val) {
visit_edge[i] = (tmp > val) + 1;
visit_edge[j] = 3 ^ visit_edge[i];
// 1 : not loyal, 2 : loyal
}
}
if (!visit_edge[i]) visit_edge[i] = 1;
for (auto j : buf) {
if (!visit_edge[j]) visit_edge[j] = visit_edge[i];
}
}
else {
vector<int> ask = vec;
for (auto &j : ask) if (j == id) j = i;
int tmp = count_common_roads(ask);
if (tmp == val) visit_edge[i] = visit_edge[id];
else visit_edge[i] = 3 ^ visit_edge[id];
for (auto j : buf) {
if (!visit_edge[j]) {
vector<int> ask = vec;
for (auto &k : ask) if (k == j) k = i;
int tmp = count_common_roads(ask);
if (tmp == val) visit_edge[j] = visit_edge[i];
else visit_edge[j] = 3 ^ visit_edge[i];
}
}
}
}
vector<int> vres;
for (int i = 0; i < m; ++i) {
if (visit_edge[i] % 2 == 0) vres.push_back(i);
}
return vres;
}
