#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;
vector<pair<int,int>>adj[mxn];
bool vis[mxn]; pair<int,int>from[mxn]; bool ok; int cur, head; vi egs, nodes, status;
mt19937 rng(1911);
void dfs(int node, int fr){
if(ok)return;
for(auto [u,id] : adj[node]){
if(ok)return;
// if(status[id]==0)continue;
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;
}
}
}
double dtime = 0, btime = 0;
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
vector<int>zero = {0}; if(n==2)return zero;
f0r(i,n)adj[i].clear(); int m = u.size(); f0r(i,m)if(u[i]>v[i])swap(u[i],v[i]);
f0r(i,m)adj[u[i]].pb(mp(v[i],i)),adj[v[i]].pb(mp(u[i],i));
vi g(n); f0r(i,m){if(u[i]+1==v[i])g[u[i]]=i; if(u[i]==0&&v[i]==n-1)g[n-1]=i;}
vi f(n); int mx = -1; vi mxd; f0r(i,n){
vi quer; f0r(j,n)if(i!=j)quer.pb(g[j]); int ret = count_common_roads(quer);
if(ret > mx)mx=ret,mxd={i}; else if(ret==mx)mxd.pb(i);
}//mx = removed bad edge
// vout(mxd); cout<<"MXD\n";
vi ans; f0r(i,n)f[i]=1; for(auto u : mxd)f[u]=0; f0r(i,n)if(f[i])ans.pb(g[i]);
// for(auto u : f)cout<<u<<' '; cout<<"F\n";
vector<vector<int>> w(n, vi(n)); f0r(i,m)w[u[i]][v[i]]=i,w[v[i]][u[i]]=i;
f0r(i,n){
//(i,i+2),(i,i+3),...,(i,n-1)
int pv = n-1, seen = 0;
while(1){
int lo = i+1, hi = pv; while(lo < hi){
int mid = lo + (hi-lo+1) / 2; //mid~n-1 connect to i, before that create chain
vi quer; int minus = 0; f0r(j,mid-1)quer.pb(g[j]),minus+=f[j]; for(int j = mid; j < n; j++)quer.pb(w[i][j]);
int ret = count_common_roads(quer); ret -= minus + seen; if(ret > 0)lo=mid; else hi=mid-1;
} if(lo<=i+1)break; ans.pb(w[i][lo]); pv = lo - 1; seen++;
}
}
set<int>gg; for(auto u : ans)gg.insert(u); vi anss; for(auto u : gg)anss.pb(u); return anss;
/*
status.resize(m); f0r(i,m)status[i]=-1; queue<int>q;
while(1){
f0r(i,n)from[i] = mp(-1,-1); cur = -1; ok = 0; egs.clear(); nodes.clear(); int rt = rng() % n;
f0r(i,n)vis[i]=0; vis[rt] = 1;
int t1 = std::chrono::system_clock::now().time_since_epoch().count(); dfs(rt,-1); int t2 = std::chrono::system_clock::now().time_since_epoch().count();
dtime += t2 - t1; //for(auto u : from)cout<<u.F<<' '<<u.S<<'\n';
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;
t1 = std::chrono::system_clock::now().time_since_epoch().count();
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);
}
}
t2 = std::chrono::system_clock::now().time_since_epoch().count(); btime += t2 - t1;
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(find(adj[u[eg]].begin(),adj[u[eg]].end(),mp(v[eg], eg))); adj[v[eg]].erase(find(adj[v[eg]].begin(),adj[v[eg]].end(),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); //dout2(dtime/1e9, btime/1e9);
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;
*/
}
/*
4
6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
