#include "simurgh.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=510;
const ll inf=1e9+900;
ll d[maxn];
vector<ll> s,t;
ll ger[maxn][maxn];
ll hast[maxn][maxn];
ll barg,N,M;
ll c_c_r(vector<ll> r){
return count_common_roads(r);
}
bool backedge[maxn*maxn];
ll yal[maxn*maxn];
vector<ll> tree;
ll highback[maxn*maxn];
ll pare[maxn*maxn];
bool vis[maxn*maxn];
ll h[maxn];
vector<ll> child[maxn];
ll treeans;
pii dfs(ll a){
vis[a]=1;
pii best=mp(h[a],0);
for(ll i=0;i<N;i++){
if(ger[a][i]!=-1){
ll e=ger[a][i];
if(!vis[i]){
child[a].pb(e);
tree.pb(e);
pare[i]=e;
h[i]=h[a]+1;
pii y=dfs(i);
best=min(best,y);
if(y.F<h[a]){
highback[e]=y.S;
}else{
highback[e]=-1;
}
}else if(h[i]>h[a]){
backedge[e]=1;
yal[e]=pare[i];
}else{
best=min(best,mp(h[i],e));
}
}
}
return best;
}
vector<pii> shart[maxn*maxn];
vector<ll> gruh[2];
void dfsShart(ll a,bool b){
gruh[b].pb(a);
vis[a]=1;
for(auto e:shart[a]){
if(!vis[e.F]){
dfsShart(e.F,e.S^b);
}
}
}
void findShart(ll a,ll b){
vector<ll> r;
for(auto e:tree){
if(e==a)r.pb(b);
else r.pb(e);
}
ll t=c_c_r(r);
if(t==treeans){
shart[a].pb(mp(b,0));
shart[b].pb(mp(a,0));
}else{
shart[a].pb(mp(b,1));
shart[b].pb(mp(a,1));
}
}
ll pardsu[maxn];
ll findpardsu(ll a){
if(pardsu[a]==a)return a;
pardsu[a]=findpardsu(pardsu[a]);
return pardsu[a];
}
vector<ll> getYal(vector<ll> g){
for(ll i=0;i<maxn;i++){
pardsu[i]=i;
}
vector<ll> r;
for(auto yal:g){
ll a=findpardsu(s[yal]);
ll b=findpardsu(t[yal]);
if(a==b){
return r;
}else{
pardsu[a]=b;
}
}
for(ll e=0;e<M;e++){
ll a=findpardsu(s[e]);
ll b=findpardsu(t[e]);
if(a!=b){
pardsu[a]=b;
r.pb(e);
}
}
for(auto e:g)r.pb(e);
return r;
}
vector<ll> solve2(ll n){
dfs(0);
treeans=c_c_r(tree);
for(ll e=0;e<M;e++){
if(h[s[e]]>h[t[e]])swap(s[e],t[e]);
if(backedge[e]){
findShart(yal[e],e);
}
}
for(auto e:tree){
if(highback[e]!=-1){
findShart(e,highback[e]);
findShart(pare[s[e]],highback[e]);
}
}
memset(vis,0,sizeof vis);
vector<ll> ans;
for(auto e:tree){
if(!vis[e]){
gruh[0].clear();
gruh[1].clear();
dfsShart(e,0);
vector<ll> r0=getYal(gruh[0]);
vector<ll> r1=getYal(gruh[1]);
if(r0.empty()){
for(auto e:gruh[1])ans.pb(e);
}
else if(r1.empty()){
for(auto e:gruh[0])ans.pb(e);
}else{
if(gruh[0].size()<gruh[1].size()){
for(auto e:gruh[1])ans.pb(e);
}
if(gruh[0].size()>gruh[1].size()){
for(auto e:gruh[0])ans.pb(e);
}
if(gruh[0].size()==gruh[1].size()){
ll d0=c_c_r(r0);
ll d1=c_c_r(r1);
if(d0>d1){
for(auto e:gruh[0])ans.pb(e);
}else{
for(auto e:gruh[1])ans.pb(e);
}
}
}
}
}
return ans;
}
ll findCnt(ll v,ll l,ll r){
vector<ll> t;
for(ll i=l;i<r;i++){
if(i!=v && i!=barg){
t.pb(ger[v][i]);
}
}
ll ans=0;
ans-=hast[v][barg];
t.pb(ger[v][barg]);
for(ll i=0;i<l;i++){
if(i!=v &&i!=barg){
t.pb(ger[barg][i]);
ans-=hast[barg][i];
}
}
for(ll i=r;i<N;i++){
if(i!=v && i!=barg){
t.pb(ger[barg][i]);
ans-=hast[barg][i];
}
}
ans+=c_c_r(t);
return ans;
}
void findHam(ll v,ll l,ll r,ll x){
if(l>=r)return;
if(x==0)return;
if(l+1==r){
hast[v][l]=1;
hast[l][v]=1;
return;
}
ll mid=(l+r)/2;
ll y=findCnt(v,l,mid);
findHam(v,l,mid,y);
findHam(v,mid,r,x-y);
}
void solve(ll n){
barg=-1;
for(ll i=0;i<n;i++){
vector<ll> r;
for(ll j=0;j<n;j++){
if(j!=i){
r.pb(ger[i][j]);
}
}
d[i]=c_c_r(r);
if(d[i]==1)barg=i;
}
for(ll i=0;i<n;i++){
if(i!=barg){
vector<ll> r;
ll yeki=-1;
for(ll j=0;j<n;j++){
if(j!=i && j!=barg){
yeki=j;
r.pb(ger[i][j]);
}
}
r.pb(ger[barg][yeki]);
if(c_c_r(r)==d[i]-1){
hast[barg][i]=1;
hast[i][barg]=1;
break;
}
}
}
for(ll i=0;i<n;i++){
if(i!=barg){
findHam(i,0,n,d[i]-hast[barg][i]);
}
}
}
vector<ll> findAnsE(ll n){
vector<ll> ans;
for(ll i=0;i<n;i++){
for(ll j=i+1;j<n;j++){
if(hast[i][j]){
ans.pb(ger[i][j]);
}
}
}
sort(ans.begin(),ans.end());
return ans;
}
vector<int> find_roads(int n,vector<int> u,vector<int> v) {
N=n;
if(n==2){
vector<ll> ans;
ans.pb(0);
return ans;
}
memset(ger,-1,sizeof ger);
s=v;
t=u;
ll m=v.size();
M=m;
for(ll i=0;i<m;i++){
ger[s[i]][t[i]]=i;
ger[t[i]][s[i]]=i;
}
if(m==(n*(n-1))/2){
solve(n);
return findAnsE(n);
}
if(n<=240){
return solve2(n);
}
exit(1);
}
