#include "simurgh.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int mxn=505;
int pa[mxn+10];
vector<int>have[mxn+10];
int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
bool merge(int a,int b){
a=find(a),b=find(b);
if(a==b)return false;
if(have[a].size()<have[b].size())swap(a,b);
pa[b]=a;
for(auto i:have[b])have[a].pb(i);
return true;
}
void init(int n){
for(int i=0;i<=n;i++){
pa[i]=i;
have[i].clear();
have[i].pb(i);
}
}
int mark[mxn+10];
int E[mxn+10][mxn+10],done[mxn+10][mxn+10];
int bro=0;
vector<int> find_roads(int n, vector<int> u,vector<int> v) {
vector<int>ans;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)E[i][j]=-1;
for(int i=0;i<u.size();i++){
E[u[i]][v[i]]=i;
E[v[i]][u[i]]=i;
}
for(int node=0;node<n;node++){
init(n);
vector<int>edge;
for(int j=0;j<u.size();j++)if(u[j]!=node&&v[j]!=node&&merge(u[j],v[j])){
edge.pb(j);
}
vector<int>head;
vector<int>addedge;
for(int i=0;i<n;i++)if(i!=node&&!mark[find(i)]){
head.pb(find(i));
for(auto j:have[find(i)])if(E[node][j]!=-1){
addedge.pb(E[node][j]);
break;
}
if(addedge.size()!=head.size())assert(0);
mark[find(i)]=1;
}
for(int i=0;i<n;i++)mark[i]=0;
for(int i=0;i<head.size();i++){
for(int j=0;j<addedge.size();j++)if(j!=i)edge.pb(addedge[j]);
int c=0,mx=0;
vector<int>val;
for(auto j:have[head[i]]){
if(E[node][j]==-1){
val.pb(-1);
continue;
}
if(j<node){
if(c>0||done[node][j]==0){
val.pb(-1);
continue;
}
c++;
}
edge.pb(E[node][j]);
bro++;
if(bro>30000)assert(0);
val.pb(count_common_roads(edge));
mx=max(mx,val.back());
edge.pop_back();
}
if(mx==0)assert(0);
for(int j=0;j<have[head[i]].size();j++)if(val[j]==mx&&have[head[i]][j]>node){
done[node][have[head[i]][j]]=1;
done[have[head[i]][j]][node]=1;
ans.pb(E[node][have[head[i]][j]]);
}
for(int j=0;j<addedge.size()-1;j++)edge.pop_back();
}
}
return ans;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
5 9
2 1
1 4
4 0
0 3
3 4
2 4
1 3
0 2
0 1
0 1 2 3
*/
