#include "simurgh.h"
#include "bits/stdc++.h"
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
vi find_roads(int n, vi u, vi v) {
int m = u.size();
vvi G(n);
vvi id(n, vi(n));
rep(i, m) {
G[u[i]].pb(v[i]);
G[v[i]].pb(u[i]);
id[u[i]][v[i]] = i;
id[v[i]][u[i]] = i;
}
vi par(n, inf);
vi dep(n);
vb on_tree(m);
vi ori_edge;
auto dfs = [&](auto &dfs, int now, int p, int d) -> void {
par[now] = p;
dep[now] = d;
for (int nx : G[now]) {
if (nx == p) continue;
if (par[nx] != inf) continue;
on_tree[id[now][nx]] = true;
ori_edge.pb(id[now][nx]);
dfs(dfs, nx, now, d + 1);
}
};
dfs(dfs, 0, -1, 0);
auto lca = [&](int i, int j) {
if (dep[i] > dep[j]) swap(i, j);
while (dep[i] < dep[j]) j = par[j];
while (i != j) {
i = par[i];
j = par[j];
}
return i;
};
const int ori = count_common_roads(ori_edge);
auto replace = [&](int add, int er) -> int {
vi tmp = {add};
for (int i : ori_edge) {
if (i != er) tmp.pb(i);
}
return count_common_roads(tmp) - ori;
};
vi ans(m, -1);
rep(i, m) {
if (on_tree[i]) continue;
assert(ans[i] == -1);
int l = lca(u[i], v[i]);
vi es;
int now = u[i];
while (now != l) {
es.pb(id[now][par[now]]);
now = par[now];
}
now = v[i];
while (now != l) {
es.pb(id[now][par[now]]);
now = par[now];
}
int alr = -1;
vi same = {(int) i}, dif;
int self = -1;
for (int j : es) {
if (ans[j] == -1) {
int r = replace(i, j);
assert(-1 <= r and r <= 1);
if (r == 0) same.pb(j);
else {
dif.pb(j);
self = (r > 0 ? 1 : 0);
}
} else {
alr = j;
}
}
if (self != -1) {
for (int j : same) ans[j] = self;
for (int j : dif) ans[j] = self ^ 1;
continue;
}
assert(dif.empty());
if (alr == -1) {
for (int j : same) ans[j] = 0;
} else {
int r = replace(i, alr);
assert(0 <= ans[alr] + r and ans[alr] + r <= 1);
for (int j : same) ans[j] = ans[alr] + r;
}
}
vi res;
rep(i, m) {
if (ans[i] == 1 or ans[i] == -1) res.pb(i);
}
assert(res.size() == n - 1);
return res;
}
