#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=505;
int N, edg[nx][nx], vl[nx][nx], dsu[nx], vs[nx], f[nx], cnt, sv[nx], def[nx], mx, resq[nx];
vector<int> g[nx], nd[nx], qrs, tem, bs, res;
vector<tuple<int, int, int>> t;
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
void dfs(int u, int st, int cur)
{
for (int v=0; v<N; v++)
{
if (vs[v]||edg[u][v]==-1) continue;
if (v==st)
{
def[cur]=u;
if (vl[u][v]>=0) sv[cur]=u;
else if (!f[u]) nd[cur].push_back(u);
}
else vs[v]=1, tem.push_back(edg[u][v]), dfs(v, st, cur);
}
}
int check(int l, int r, int st)
{
//cout<<"here "<<st<<' '<<l<<' '<<r<<'\n';
qrs.clear();
int expected=0;
for (int i=l; i<=r; i++) dsu[find(bs[i])]=find(st), qrs.push_back(edg[st][bs[i]]);
//cout<<"before ";
//for (auto x:qrs) cout<<x<<' ';
//cout<<'\n';
for (auto [u, v, w]:t) if (find(u)!=find(v)) expected+=w, dsu[find(u)]=find(v), qrs.push_back(edg[u][v]);
if (count_common_roads(qrs)>expected) return 1;
return 0;
}
std::vector<int> find_roads(int n, std::vector<int> _u, std::vector<int> _v) {
N=n;
for (int i=0; i<n; i++) for (int j=0; j<n; j++) edg[i][j]=-1;
for (int i=0; i<_u.size(); i++) edg[_u[i]][_v[i]]=edg[_v[i]][_u[i]]=i;
for (int i=0; i<n; i++) for (int j=0; j<n; j++) vl[i][j]=-1;
queue<int> q;
q.push(0);
f[0]=1;
while (!q.empty())
{
auto u=q.front();
q.pop();
cnt=0;
for (int i=0; i<n; i++) vs[i]=0;
tem.clear();
for (int v=0; v<n; v++)
{
if (edg[u][v]==-1||vs[v]) continue;
sv[cnt]=-1;
vs[v]=1;
dfs(v, u, cnt);
cnt++;
}
//cout<<"debug "<<u<<' '<<cnt<<'\n';
for (int i=0; i<cnt; i++)
{
if (nd[i].empty()) continue;
//cout<<"here "<<i<<' '<<sv[i]<<' '<<def[i]<<'\n';
qrs=tem;
for (int j=0; j<cnt; j++) if (i!=j) qrs.push_back(edg[u][def[j]]);
if (sv[i]==-1)
{
mx=0;
int sz=nd[i].size();
for (int j=0; j<sz; j++)
{
qrs.push_back(edg[u][nd[i][j]]);
resq[j]=count_common_roads(qrs);
qrs.pop_back();
mx=max(mx, resq[j]);
}
for (int j=0; j<sz; j++)
{
int v=nd[i][j];
f[v]=1;
q.push(v);
vl[u][v]=vl[v][u]=(resq[j]==mx);
t.push_back({u, v, vl[u][v]});
}
}
else
{
qrs.push_back(edg[u][sv[i]]);
int ref=count_common_roads(qrs);
qrs.pop_back();
int sz=nd[i].size();
for (int j=0; j<sz; j++)
{
int v=nd[i][j];
qrs.push_back(edg[u][v]);
int ans=count_common_roads(qrs);
qrs.pop_back();
f[v]=1;
q.push(v);
if (ans<ref) vl[u][v]=vl[v][u]=0;
if (ans==ref) vl[u][v]=vl[v][u]=vl[u][sv[i]];
if (ans>ref) vl[u][v]=vl[v][u]=1;
t.push_back({u, v, vl[u][v]});
}
}
}
for (int i=0; i<cnt; i++) g[i].clear(), nd[i].clear();
}
//for (auto [u, v, w]:t) cout<<"t "<<u<<' '<<v<<' '<<w<<'\n';
for (int u=0; u<n; u++)
{
while (1)
{
bs.clear();
for (int v=0; v<n; v++) if (edg[u][v]!=-1&&vl[u][v]==-1) bs.push_back(v);
int l=0, r=bs.size()-1;
if (bs.empty()) break;
for (int i=0; i<n; i++) dsu[i]=i;
if (check(l, r, u))
{
while (l<r)
{
int md=(l+r)/2;
for (int i=0; i<n; i++) dsu[i]=i;
if (check(l, md, u)) r=md;
else
{
for (int i=l; i<=md; i++) vl[u][bs[i]]=vl[bs[i]][u]=0;
l=md+1;
}
}
vl[u][bs[l]]=vl[bs[l]][u]=1;
}
else
{
for (auto x:bs) vl[u][x]=vl[x][u]=0;
break;
}
}
}
for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) if (vl[i][j]==1) res.push_back(edg[i][j]);
//for (auto x:res) cout<<x<<' ';
//cout<<'\n';
return res;
}
/*
4 4
0 1
1 2
1 3
2 3
0 1 2
*/
