#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=507,M=507*507;
int U[M],V[M];
int n;
vector<pair<int,int>>G[N];
int odw[N],c;
int o[N],id[N];
vector<int>st;
int val[M];
void dfs(int v)
{
odw[v]=++c;
for(auto [u,i]:G[v])
{
if(!odw[u])
{
o[u]=v;
id[u]=i;
st.pb(i);
dfs(u);
}
}
}
int get(int x)
{
vector<int>Q;
for(auto y:st) if(y!=x) Q.pb(y);
return count_common_roads(Q);
}
void dfs1(int v)
{
odw[v]=++c;
for(auto [u,i]:G[v])
{
if(!odw[u]) dfs1(u);
else if(odw[u]<odw[v]&&u!=o[v])
{
vector<int>X={i};
st.pb(i);
int p=-1,x=v;
while(x!=u)
{
if(val[id[x]]) p=id[x];
else X.pb(id[x]);
x=o[x];
}
if(sz(X)==1)
{
st.pop_back();
continue;
}
if(p==-1)
{
vector<pair<int,int>>W;
int mx=-inf;
for(auto x:X)
{
int k=get(x);
mx=max(mx,k);
W.pb({k,x});
}
for(auto [k,x]:W)
{
if(k<mx) val[x]=2;
else val[x]=1;
}
}
else
{
for(auto x:X)
{
int c1=get(p),c2=get(x);
if(c1==c2) val[x]=val[p];
else if(c1<c2) val[x]=1;
else val[x]=2;
}
}
st.pop_back();
}
}
if(!val[id[v]]) val[id[v]]=2;
}
bool was[M];
vector<int>co[N];
int r[N];
int Find(int v)
{
if(r[v]==v) return v;
return r[v]=Find(r[v]);
}
void Union(int v,int u)
{
u=Find(u),v=Find(v);
r[u]=v;
}
int ile;
int qry(vector<int>W)
{
vector<int>Q;
for(int i=0;i<n;i++) r[i]=i;
for(auto x:W)
{
Union(U[x],V[x]);
Q.pb(x);
}
int k=ile;
for(auto x:st)
{
if(Find(U[x])==Find(V[x])) k-=val[x]-1;
else
{
Union(U[x],V[x]);
Q.pb(x);
}
}
return count_common_roads(Q)-k;
}
vector<int>find_roads(int nn,vector<int>uu,vector<int>vv)
{
n=nn;
int m=sz(uu);
for(int i=0;i<m;i++)
{
U[i]=uu[i];
V[i]=vv[i];
if(U[i]>V[i]) swap(U[i],V[i]);
G[U[i]].pb({V[i],i});
G[V[i]].pb({U[i],i});
}
dfs(0);
memset(odw,0,sizeof odw);
dfs1(0);
for(auto x:st) was[x]=1;
for(int i=0;i<m;i++)
{
if(!was[i]) co[U[i]].pb(i);
}
ile=count_common_roads(st);
for(int i=0;i<n;i++)
{
vector<int>Q;
for(auto x:co[i]) Q.pb(x);
int deg=qry(Q);
for(int j=1;j<=deg;j++)
{
int l=0,r=sz(co[i])-1,sr,p;
while(l<=r)
{
sr=(l+r)/2;
Q.clear();
for(int k=0;k<=sr;k++) Q.pb(co[i][k]);
if(qry(Q)>=j)
{
r=sr-1;
p=sr;
}
else l=sr+1;
}
val[co[i][p]]=2;
}
}
vector<int>ans;
for(int i=0;i<m;i++) if(val[i]==2) ans.pb(i);
return ans;
}
/*
int main()
{
vector<int>X=find_roads(4,{0, 0, 0, 1, 1, 2},{1, 2, 3, 2, 3, 3});
return 0;
}*/
