#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=3e5+10;
const int MAXL=11;
const int inf=1e6;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
int n,pai[MAXN],peso[MAXN],edgeid[MAXN],is_on[MAXM];
bool z[MAXN];
vector<int> ans;
vector<pii> g[MAXN],to_query[MAXN];
vector<trio> mst;
int find(int x){
return x==pai[x]?x:pai[x]=find(pai[x]);
}
void merge(int a,int b){
a=find(a),b=find(b);
if(peso[a]==peso[b]){
pai[a]=b;
peso[b]++;
return;
}
if(peso[a]>peso[b]) swap(a,b);
pai[a]=b;
}
int quantas(vector<pii> v,int x){
vector<int> sub;
fall(i,0,n-1) pai[i]=i,peso[i]=0;
for(auto [u,j]:v){
merge(u,x);
sub.pb(j);
}
int ad=0;
for(auto [a,b,c]:mst){
if(find(b)!=find(c)){
sub.pb(a);
merge(b,c);
ad+=is_on[a];
}
}
return count_common_roads(sub)-ad;
}
void dnc(vector<pii> v,int x,int q){
if(!q) return;
if(sz(v)==1){
ans.pb(v[0].second);
return;
}
int m=(sz(v)-1)>>1;
vector<pii> g1,g2;
fall(i,0,m) g1.pb(v[i]);
fall(i,m+1,sz(v)-1) g2.pb(v[i]);
int val=quantas(g1,x); dnc(g1,x,val);dnc(g2,x,q-val);
}
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});
auto dfs=[&](auto &&self,int x,int p,bool flag)->void{
fall(j,0,n-1) pai[j]=j,peso[j]=0,edgeid[j]=-1,to_query[j].clear();
vector<int> arestas;
fall(i,0,sz(u)-1){
if(u[i]==x || v[i]==x) continue;
if(find(u[i])!=find(v[i])){
merge(u[i],v[i]);
arestas.pb(i);
}
}
fall(j,0,n-1){
if(j==x || pai[j]!=j) continue;
edgeid[j]=sz(arestas);
bool fd=0;
for(auto [u,num]:g[x]){
if(find(u)==j && !fd){
fd=1;
arestas.pb(num);
}
if(find(u)==j && (!z[u] || u==p)) to_query[j].pb({u,num});
}
}
vector<pii> lista;
fall(j,0,n-1){
if(!sz(to_query[j])) continue;
if(p!=-1 && find(p)==j){
int valor=0;
for(auto [u,id]:to_query[j])
if(u==p){
arestas[edgeid[j]]=id;
valor=count_common_roads(arestas);
break;
}
valor+=(!flag);
for(auto [u,id]:to_query[j]){
z[u]=1;
if(u==p) continue;
arestas[edgeid[j]]=id;
if(count_common_roads(arestas)==valor) is_on[id]=1;
mst.pb({id,u,x});
lista.pb({u,is_on[id]});
}
}
else{
int mx=-1;
vector<int> lig;
for(auto [u,id]:to_query[j]){
arestas[edgeid[j]]=id;
int c=count_common_roads(arestas);
if(c>mx){
mx=c;
lig.clear(); lig.pb(id);
}
else if(c==mx) lig.pb(id);
z[u]=1;
}
for(auto u:lig) is_on[u]=1;
for(auto [u,id]:to_query[j]){
mst.pb({id,u,x});
lista.pb({u,is_on[id]});
}
}
}
for(auto [u,j]:lista) self(self,u,x,j);
};
dfs(dfs,0,-1,0);
fall(i,0,n-1){
vector<pii> cand;
for(auto [u,j]:g[i]){
if(u<i) continue;
cand.pb({u,j});
}
dnc(cand,i,quantas(cand,i));
}
return ans;
}
