#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int n, counter=0;
vector<bool> in, visited;
vector<int> isroyal, low, disc, epar, par, up, ooga, tree, deg, dsu;
vector<pii> edges;
vector<vector<pii> > graph;
int query(){
vector<int> temp;
for (int i=0; i<in.size(); ++i)if (in[i])temp.pb(i);
return count_common_roads(temp);
}
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
bool merge(int a, int b){
a=fp(a), b=fp(b);
if (a==b)return 0;
dsu[a]=b;
return 1;
}
void dfs(int node, int p, int ep){
par[node]=p;
epar[node]=ep;
disc[node]=low[node]=++counter;
for (auto num:graph[node])if (num.se!=ep){
if (disc[num.fi]==-1){
dfs(num.fi, node, num.se);
if (low[num.fi]<low[node])low[node]=low[num.fi], up[node]=up[num.fi];
if (low[num.fi]>disc[node])isroyal[num.se]=1;
}
else if (low[node]>disc[num.fi])low[node]=disc[num.fi], up[node]=num.se;
}
if (ep!=-1)in[ep]=1, tree.pb(ep);
}
void dfs2(int node){
for (auto num:graph[node])if (par[num.fi]==node)dfs2(num.fi);
if (par[node]==-1||up[node]==-1||isroyal[up[node]]!=-1)return;
int a=edges[up[node]].fi, b=edges[up[node]].se;
if (disc[a]>disc[b])swap(a, b);
int mx=query(), mn=mx, r=-1;
in[up[node]]=1;
for (int c=b; c!=a; c=par[c]){
in[epar[c]]=0;
ooga[epar[c]]=query();
mn=min(mn, ooga[epar[c]]);
mx=max(mx, ooga[epar[c]]);
if (isroyal[epar[c]]!=-1)r=ooga[epar[c]]-!isroyal[epar[c]];
in[epar[c]]=1;
}
in[up[node]]=0;
for (int c=b; c!=a; c=par[c])if (isroyal[epar[c]]==-1){
if (r!=-1)isroyal[epar[c]]=(r==ooga[epar[c]]);
else if (mn==mx)isroyal[epar[c]]=0;
else isroyal[epar[c]]=(ooga[epar[c]]==mn);
}
}
int query_forest(vector<int> vect){
int res=0;
dsu.assign(n, -1);
vector<int> del;
for (auto c:vect)del.pb(c), merge(edges[c].fi, edges[c].se), in[c]=1;
for (auto c:tree)if (merge(edges[c].fi, edges[c].se))del.pb(c), in[c]=1, res-=isroyal[c];
res+=query();
for (auto a:del)in[a]=0;
return res;
}
void cut(int node){
if (!deg[node]||visited[node])return;
visited[node]=1;
vector<int> e;
for (auto num:graph[node])if (!visited[num.fi])e.pb(num.se);
int low=-1, high=e.size()-1;
while (low+1<high){
int mid=(low+high)/2;
vector<int> temp;
for (int i=low+1; i<=mid; ++i)temp.pb(e[i]);
if (query_forest(temp))high=mid;
else low=mid;
}
int p=edges[e[high]].fi^edges[e[high]].se^node;
isroyal[e[high]]=1;
--deg[p];
if (deg[p]==1)cut(p);
}
vector<int> find_roads(int N, vector<int> u, vector<int> v){
n=N;
epar.resize(n);
par.resize(n);
graph.resize(n);
low.resize(n);
up.resize(n, -1);
disc.resize(n, -1);
in.resize(u.size(), 0);
deg.resize(n);
ooga.resize(u.size());
isroyal.resize(u.size(), -1);
for (int i=0; i<u.size(); ++i){
edges.pb(mp(u[i], v[i]));
graph[u[i]].pb(mp(v[i], i));
graph[v[i]].pb(mp(u[i], i));
}
dfs(0, -1, -1);
dfs2(0);
in.assign(u.size(), 0);
for (int i=0; i<n; ++i){
vector<int> temp;
for (auto num:graph[i])temp.pb(num.se);
deg[i]=query_forest(temp);
}
visited.resize(n, 0);
for (int i=0; i<n; ++i)if (deg[i]==1)cut(i);
vector<int> ans;
for (int i=0; i<u.size(); ++i)if (isroyal[i]==1)ans.pb(i);
return ans;
}
