#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;
#define gout(v) cout<<#v<<": "; vout(v);
using namespace std;
const int mxn = 505;
vector<pair<int,int>>adj[mxn];
bool vis[mxn]; pair<int,int>par[mxn]; bool ok; int cur, head; vi egs, nodes, status, ans; vector<bool>ontree;
int tin[mxn], sz[mxn], timer = 0;
double dtime = 0, btime = 0;
mt19937 rng(1911);
void dfs(int node, int from){
tin[node] = timer++; sz[node] = 1;
for(auto [u,id] : adj[node]){
if(!vis[u]){
vis[u] = 1, par[u] = mp(node, id), ontree[id] = 1; dfs(u, node); sz[node] += sz[u];
}
}
}
bool insub(int x, int y){
return (tin[x] <= tin[y] && tin[y] <= tin[x] + sz[x] - 1);
}
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));
status.resize(m); f0r(i,m)status[i]=-1; queue<int>q; ontree.resize(m); vis[0] = 1; par[0] = mp(-1,-1); dfs(0,-1);
vi tredges; f0r(i,m)if(ontree[i])tredges.pb(i); //cout<<"tredges: "; vout(tredges);
f0r(i,m)if(ontree[i] && status[i] == -1){
// cout<<"checking "<<i<<'\n';
int x, y; if(par[u[i]].first == v[i])x=v[i],y=u[i]; else x=u[i],y=v[i];
int backedge = -1, tp, bt;
f0r(j,m)if(!ontree[j]){
if(insub(u[j], x) && insub(y, v[j])){tp = u[j], bt = v[j], backedge = j; break;}
else if(insub(v[j], x) && insub(y, u[j])){tp = v[j], bt = u[j], backedge = j; break;}
else continue;
}
if(backedge == -1){status[i] = 1; continue;}
vi cyc; int cur = bt; set<int>fix; for(auto u : tredges)fix.insert(u);
while(cur != tp){
cyc.pb(par[cur].S); fix.erase(par[cur].S); cur = par[cur].F;
} cyc.pb(backedge); vi qq; for(auto u : fix)qq.pb(u);
// cout<<"cyc: "; vout(cyc);
int mx = -1, control = -1, ct = 0; set<int>rem; for(auto eg : cyc){
if(status[eg] == 0 && control == -1){
vi quer = qq; for(auto ed : cyc)if(ed != eg)quer.pb(ed);
int ret = count_common_roads(quer); control = ret; continue;
}
if(status[eg] != -1)continue;
ct++; vi quer = qq; for(auto ed : cyc)if(ed != eg)quer.pb(ed);
int ret = count_common_roads(quer); if(ret > mx)mx = ret, rem.clear(), rem.insert(eg); else if(ret == mx)rem.insert(eg);
}
// cout<<"rem: "; vout(rem);
for(auto eg : cyc){
if(status[eg] != -1)continue;
if(rem.count(eg) && ct == rem.size() && control > mx)status[eg] = 1;
else if(rem.count(eg)){
status[eg] = 0;
}
else status[eg] = 1;
}
}
set<int>ass; f0r(i,m)if(status[i] == 1)ass.insert(i); vector<vector<pair<int,int>>> be(n); f0r(i,m)if(!ontree[i]){
if(tin[u[i]] < tin[v[i]])be[u[i]].pb(mp(v[i],i)); else be[v[i]].pb(mp(u[i],i));
}
int model = 0; for(auto u : tredges)if(status[u]==1)model++;
f0r(x, n){
int pv = 0;
while(1){
int lo = pv, hi = be[x].size(); while(lo < hi){
int mid = lo + (hi-lo) / 2, tmp = model; set<int>qu; for(auto u : tredges)qu.insert(u); for(int i = pv; i <= mid; i++){
int node = be[x][i].F; qu.erase(par[node].S); tmp -= status[par[node].S]; qu.insert(be[x][i].S);
} vi quer; for(auto u : qu)quer.pb(u); int ret = count_common_roads(quer); if(ret > tmp)hi=mid; else lo=mid+1;
} if(lo == be[x].size())break; ass.insert(be[x][lo].S); pv = lo + 1;
}
}
for(auto u : ass)ans.pb(u); return ans;
/*
f0r(i,n){
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
*/
