#include "simurgh.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i < n; i++)
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int mxn = 505;
set<pair<int,int>>adj[mxn];
vector<bool>vis; vector<pair<int,int>>from; bool ok; int cur, head; vi egs, nodes;
void dfs(int node, int fr){
if(ok)return;
for(auto [u,id] : adj[node]){
if(ok)return;
if(!vis[u]){
vis[u] = 1, from[u] = mp(node, id); dfs(u, node);
}
else if(u != fr){
cur = node, head = u; egs.pb(id); ok = 1; return;
}
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
f0r(i,n)adj[i].clear(); int m = u.size(); f0r(i,m)adj[u[i]].insert(mp(v[i],i)),adj[v[i]].insert(mp(u[i],i));
vi status(m, -1); from.resize(n); vis.resize(n); queue<int>q;
while(1){
f0r(i,n)from[i] = mp(-1,-1); cur = -1; ok = 0; egs.clear(); nodes.clear();
f0r(i,n)vis[i]=0; vis[0] = 1;
dfs(0,-1); //for(auto u : from)cout<<u.F<<' '<<u.S<<'\n';
/*
while(!q.empty()){
int node = q.front(); q.pop(); for(auto [u,id] : adj[node]){
if(!vis[u]){
vis[u] = 1; from[u] = mp(node, id); q.push(u);
}
else if(u != from[node].F){
cur = node; ok = 1; break;
}
} if(ok)break;
}
*/
if(cur==-1)break; while(1){
nodes.pb(cur); if(from[cur].S != -1)egs.pb(from[cur].S); cur = from[cur].F; nodes.pb(cur); if(cur==head)break;
}
int mn = -1; set<int>rem; //vout(nodes);
// cout<<"egs "; for(auto u : egs)cout<<u<<' '; cout<<'\n';
vi qq; vector<bool>vis(n); for(auto u : nodes)q.push(u), vis[u] = 1;
while(!q.empty()){
int node = q.front(); q.pop(); for(auto [u,id] : adj[node]){
if(!vis[u])vis[u]=1, qq.pb(id), q.push(u);
}
}
for(auto eg : egs){
if(status[eg] != -1)continue;
vi quer = qq; for(auto ed : egs)if(ed != eg)quer.pb(ed);
int ret = count_common_roads(quer); if(ret > mn)mn = ret, rem.clear(), rem.insert(eg); else if(ret == mn)rem.insert(eg);
}
for(auto eg : egs){
if(rem.count(eg)){
adj[u[eg]].erase(mp(v[eg], eg)); adj[v[eg]].erase(mp(u[eg],eg)); status[eg] = 0;
}
else status[eg] = 1;
} //vout(status);
// int sum = 0; f0r(i,n)sum+=adj[i].size(); sum/=2; //dout(sum);
} f0r(i,m)if(status[i]==-1)status[i]=1;
vi ans; f0r(i,m)if(status[i] == 1)ans.pb(i); return ans;
/*
std::vector<int> r(n - 1);
for(int i = 0; i < n - 1; i++)
r[i] = i;
int common = count_common_roads(r);
if(common == n - 1)
return r;
r[0] = n - 1;
return r;
*/
}
