#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) {
if (n == 2) {
return {0};
}
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;
}
if(n <= 240) {
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;
} else {
vi ans(m, -1);
vi ori_edge;
rep2(i, 1, n) ori_edge.eb(id[0][i]);
int ori = count_common_roads(ori_edge);
rep2(i, 1, n) {
int j = (i == n - 1 ? i - 1 : i + 1);
vi ex_i, ex_j;
rep2(k, 1, n) {
if (k != i) ex_i.pb(id[0][k]);
if (k != j) ex_j.pb(id[0][k]);
}
ex_i.pb(id[i][j]);
ex_j.pb(id[i][j]);
int a = count_common_roads(ex_i) - ori;
int b = count_common_roads(ex_j) - ori;
if (a != 0) {
ans[id[0][i]] = (a > 0 ? 0 : 1);
continue;
}
if (b != 0) {
int t = (b > 0 ? 0 : 1);
ans[id[0][i]] = t + b - a;
continue;
}
ans[id[0][i]] = 0;
}
rep2(i, 1, n - 1) {
auto calc = [&](int j) {
assert(i + 1 < j and j <= n);
vi tmp;
int res = 0;
rep(k, j) if (k != i) {
tmp.pb(id[i][k]);
if (k < i) res -= ans[id[i][k]];
}
rep2(k, j, n) {
tmp.pb(id[0][k]);
res -= ans[id[0][k]];
}
res += count_common_roads(tmp);
return res;
};
rep2(j, i + 1, n) ans[id[i][j]] = 0;
int num = calc(n);
rep2(j, 1, num + 1) {
int ok = n, ng = i + 1;
while (ok - ng > 1) {
int mid = (ok + ng) / 2;
(calc(mid) >= j ? ok : ng) = mid;
}
ans[id[i][ng]] = 1;
}
}
vi res;
rep(i, m) {
assert(ans[i] != -1);
if (ans[i]) res.pb(i);
}
assert(res.size() == n - 1);
return res;
}
}
