#include "simurgh.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x);
#define rmax(r, x) r = max(r, x);
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 505;
const int maxm = maxn * maxn;
int n, m, K;
pii pa[maxn];
bool visited[maxn], used[maxm];
int gold[maxm], k[maxm], h[maxn];
vector<pii> edge, adj[maxn], ch[maxn], bk[maxn], rbk[maxn];
vector<int> dfs_tree;
int count_common_roads(const vector<int>& r);
int count_k(vector<int> v, vector<pii> rep) {
vector<int> q;
for(auto [add, sub] : rep) q.eb(add);
int i = 0, j = 0;
while(i < v.size()) {
if(j < rep.size() && v[i] == rep[j].se) {
++i;
++j;
continue;
}
q.eb(v[i++]);
}
return count_common_roads(q);
}
void dfs(int u, int p) {
visited[u] = true;
for(auto [v, i] : adj[u]) if(v != p && !used[i]) {
used[i] = true;
if(visited[v]) {
bk[u].eb(i, ch[v].back().se);
rbk[v].eb(u, i);
continue;
}
dfs_tree.eb(i);
ch[u].eb(v, i);
pa[v] = {u, i};
h[v] = h[u] + 1;
dfs(v, u);
}
}
void solve_tree(int u) {
sort(all(rbk[u]), [&](pii a, pii b) { return h[a.fi] > h[b.fi]; });
for(auto [v, i] : rbk[u]) {
vector<int> tedge;
bool all = true, no = true;
while(v != u) {
tedge.eb(pa[v].se);
if(gold[tedge.back()] != -1) all = false;
else no = false;
v = pa[v].fi;
}
if(no) continue;
if(all) {
int nk = n, xk = 0;
for(auto j : tedge) {
vector<pii> dum; dum.eb(i, j);
k[j] = count_k(dfs_tree, dum);
rmin(nk, k[j]);
rmax(xk, k[j]);
}
if(nk != xk) {
gold[i] = nk - (K - 1);
for(auto j : tedge) gold[j] = (nk == k[j]);
}
else {
if(nk == K - 1) {
for(auto j : tedge) gold[j] = true;
gold[i] = false;
}
else for(auto j : tedge) gold[j] = false;
}
}
else {
for(auto j : tedge) if(gold[j] != -1) {
vector<pii> dum; dum.eb(i, j);
gold[i] = count_k(dfs_tree, dum) - K + gold[j];
break;
}
for(auto j : tedge) if(gold[j] == -1) {
vector<pii> dum; dum.eb(i, j);
gold[j] = K + gold[i] - count_k(dfs_tree, dum);
}
}
}
for(auto [v, i] : ch[u]) solve_tree(v);
}
void solve_back(vector<pii> e, int l, int r, int cnt) {
// count_k = K - S(gold[sub]) + S(gold[add])
// S(gold[add]) = count_k - K + S(gold[sub])
if(l > r) return;
if(cnt == 0) {
for(auto [add, sub] : e) gold[add] = false;
return;
}
if(cnt == r - l + 1) {
for(auto [add, sub] : e) gold[add] = true;
return;
}
int mid = l + r >> 1;
vector<pii> t;
for(int i = mid + 1; i <= r; ++i) {
t.eb(e.back());
e.pop_back();
}
reverse(all(t));
int ret = count_k(dfs_tree, e) - K;
for(auto [add, sub] : e) ret += gold[sub];
solve_back(e, l, mid, ret);
solve_back(t, mid + 1, r, cnt - ret);
}
std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
n = _n, m = u.size();
for(int i = 0; i < m; ++i) {
edge.eb(u[i], v[i]);
adj[u[i]].eb(v[i], i);
adj[v[i]].eb(u[i], i);
}
dfs(0, -1);
sort(all(dfs_tree));
K = count_k(dfs_tree, vector<pii>());
memset(gold, -1, sizeof(gold));
solve_tree(0);
for(int i = 0; i < n; ++i) if(!bk[i].empty()) {
sort(all(bk[i]), [](pii a, pii b) { return a.se < b.se; });
vector<pii> v;
for(auto t : bk[i]) if(gold[t.fi] == -1) v.eb(t);
if(!v.empty()) {
int cnt = count_k(dfs_tree, v) - K;
for(auto [add, sub] : v) cnt += gold[sub];
solve_back(v, 0, v.size() - 1, cnt);
}
}
vector<int> ans;
for(int i = 0; i < m; ++i) if(gold[i]) ans.eb(i);
return ans;
}
