#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define F first
const int MAXN=5e2+10;
const int MAXM=3e4+10;
const int MAXL=11;
const int inf=1e6;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
int n,pai[MAXN],mn[MAXN],dep[MAXN],at,sparse[MAXN][MAXL],sp[MAXN],lca[MAXN][MAXN];
vector<pii> g[MAXN];
vector<int> g1[MAXN];
vector<int> curset,ans;
bool z[MAXM],is_on[MAXM];
int find(int x){
return x==pai[x]?x:pai[x]=find(pai[x]);
}
void join(int a,int b){
a=find(a),b=find(b);
pai[a]=b;
}
void dfs1(int x,int p){
sparse[x][0]=p;
dep[x]=dep[p]+1;
fall(i,1,MAXL-1) sparse[x][i]=sparse[sparse[x][i-1]][i-1];
for(auto u:g1[x]) if(u!=p) dfs1(u,x);
}
int get_lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
rfall(i,MAXL-1,0){
if(dep[a]-(1<<i)>=dep[b]) a=sparse[a][i];
}
if(a==b) return a;
rfall(i,MAXL-1,0) if(sparse[a][i]!=sparse[b][i]) a=sparse[a][i],b=sparse[b][i];
return sparse[a][0];
}
void dfs(int x,int p){
mn[x]=inf;
int ida=0;
for(auto [u,id]:g[x]){
if(u==p) ida=id;
if(lca[u][x]==x && dep[u]==dep[x]+1){
dfs(u,x);
mn[x]=min(mn[u],mn[x]);
if(mn[u]==mn[x] && mn[u]<dep[x]) sp[x]=sp[u];
}
}
vector<int> cand;
for(auto u:curset) if(u!=ida) cand.pb(u);
for(auto [u,id]:g[x]){
if(lca[u][x]==x || !is_on[id]) continue;
int nv=dep[get_lca(u,x)];
mn[x]=min(mn[x],nv);
if(mn[x]==nv) sp[x]=id;
}
int a;
if(mn[x]<dep[x]){
cand.pb(sp[x]);
a=count_common_roads(cand);
cand.pop_back();
}
vector<trio> vals;
int mx=0;
for(auto [u,id]:g[x]){
if(lca[u][x]==x || z[id]) continue;
z[id]=1;
if(mn[x]<dep[x]){
cand.pb(id);
int b=count_common_roads(cand);
if(a==b){
is_on[id]=1;
ans.pb(id);
int nv=dep[lca[u][x]];
mn[x]=min(mn[x],nv);
if(mn[x]==nv) sp[x]=id;
}
cand.pop_back();
}
else{
cand.pb(id);
a=count_common_roads(cand);
vals.pb({id,u,a});
mx=max(mx,a);
cand.pop_back();
}
}
for(auto [id,u,j]:vals){
if(j==mx){
is_on[id]=1;
ans.pb(id);
int nv=dep[lca[u][x]];
mn[x]=min(mn[x],nv);
if(mn[x]==nv) sp[x]=id;
}
}
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v){
n=N;
fall(i,0,sz(u)-1){
g[u[i]].pb({v[i],i}),g[v[i]].pb({u[i],i});
}
fall(i,0,n-1) pai[i]=i;
fall(x,0,n-1){
for(auto u:g[x]) if(find(u.F)!=find(x)){
join(u.F,x);
g1[u.F].pb(x),g1[x].pb(u.F);
curset.pb(u.second);
}
}
at=count_common_roads(curset);
dfs1(0,0);
fall(i,0,n-1)
fall(j,0,n-1) lca[i][j]=get_lca(i,j);
dfs(0,0);
return ans;
}
