//#pragma once
//#include "grader.cpp"
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
int to,ind;
};
vector<int>otg,h,f,rv,ru;
vector<cell>v[505];
int n,m,used[505][505],lead[505],sz[505],mas[505];
void force(int el)
{
int br,ind;
for(int i=0;i<n;i++)
{
br=0;
for(int j=0;j<v[i].size();j++)
{
if(used[i][v[i][j].to])continue;
br++;
ind=j;
}
if(br==1)
{
used[i][v[i][ind].to]=el;
used[v[i][ind].to][i]=el;
otg.push_back(v[i][ind].ind);
f.push_back(v[i][ind].ind);
}
}
}
int get_lead(int beg)
{
if(lead[beg]==beg)return beg;
return lead[beg]=get_lead(lead[beg]);
}
void prec()
{
for(int i=0;i<n;i++)
{
lead[i]=i;
sz[i]=1;
}
}
void add(int a,int b,int ind)
{
a=get_lead(a);
b=get_lead(b);
if(a==b)return;
h.push_back(ind);
if(sz[a]<sz[b])swap(a,b);
lead[b]=a;
sz[a]+=sz[b];
}
void get_tree(int beg)
{
prec();
h.clear();
for(int i=0;i<f.size();i++)
{
add(rv[f[i]],ru[f[i]],f[i]);
}
for(int i=0;i<n;i++)
{
if(i==beg)continue;
for(int j=0;j<v[i].size();j++)
{
if(used[i][v[i][j].to]==2||v[i][j].to==beg)continue;
add(i,v[i][j].to,v[i][j].ind);
}
}
}
void find_ver(int beg)
{
int ma=0,w;
get_tree(beg);
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i].to;
if(used[beg][w]==1)
{
h.push_back(v[beg][i].ind);
ma=count_common_roads(h);
h.pop_back();
break;
}
}
int c;
memset(mas,0,sizeof(mas));
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i].to;
if(!used[beg][w])
{
h.push_back(v[beg][i].ind);
c=count_common_roads(h);
ma=max(ma,c);
mas[i]=c;
h.pop_back();
}
}
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i].to;
if(mas[i]==0)continue;
if(mas[i]!=ma)used[w][beg]=3;
if(mas[i]==ma)
{
used[w][beg]=1;
otg.push_back(v[beg][i].ind);
}
}
}
vector<int> find_roads(int N, vector<int> U, vector<int> V)
{
n=N;
m=U.size();
for(int i=0;i<m;i++)
{
cell h;
h.ind=i;
h.to=V[i];
v[U[i]].push_back(h);
h.to=U[i];
v[V[i]].push_back(h);
}
rv=V;
ru=U;
for(int i=1;i<=n;i++)
{
force(2);
}
/*for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<used[i][j]<<" ";
}
cout<<endl;
}*/
for(int i=0;i<n;i++)
{
find_ver(i);
}
return otg;
}
