#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m;
vector<vector<pair<int, int>>> graph, tree, backedge;
vector<bool> bl;
vector<bool> royal;
vector<int> depth;
vector<int> cur;
vector<pair<int, int>> DD;
int X;
void dfs0(int nd, int d = 0, int pi = -1){
bl[nd] = 1;
depth[nd] = d;
for(auto [x, i]: graph[nd]) if(i != pi) {
if(bl[x]){
if(depth[x] < depth[nd]) backedge[nd].pb({x, i});
}
else{
bl[x] = 1;
tree[nd].pb({x, i});
cur.pb(i);
dfs0(x, d+1, i);
}
}
}
int ND;
pair<int, int> D;
void dfs_find(int nd, int ss = -1){
if(DD[nd].f != -1 && depth[DD[nd].f] < depth[D.f]) D = DD[nd];
if(depth[nd] < depth[ND]) return;
for(auto [x, i]: graph[nd]) if(royal[i] && x != ss) dfs_find(x, nd);
}
void dfs(int nd, int i){
for(auto [x, j]: tree[nd]) dfs(x, j);
if(i == -1) return;
ND = nd;
D = {nd, i};
dfs_find(nd);
auto it = find(cur.begin(), cur.end(), i);
if(depth[nd] <= depth[D.f]){
vector<int> ge, eq = {i};
pair<int, int> eq_mn = D, ge_mn = D;
for(auto [x, j]: backedge[nd]){
*it = j;
int c = count_common_roads(cur);
if(c == X){
eq.pb(j);
if(depth[x] < depth[eq_mn.f]) eq_mn = {x, j};
}
else if(c > X){
ge.pb(j);
if(depth[x] < depth[ge_mn.f]) ge_mn = {x, j};
}
}
*it = i;
if(ge.empty()) for(int j: eq) royal[j] = 1;
else for(int j: ge) royal[j] = 1;
if(ge.empty()) DD[nd] = eq_mn;
else DD[nd] = ge_mn;
}
else{
*it = D.sc;
int Y = count_common_roads(cur);
for(auto [x, j]: backedge[nd]){
*it = j;
int c = count_common_roads(cur);
if(c == Y){
royal[j] = 1;
if(depth[x] < depth[D.f]) D = {x, j};
}
}
*it = i;
if(X == Y) royal[i] = 1;
DD[nd] = D;
}
}
vector<int> find_roads(int _n, vector<int> U, vector<int> V){
swap(n, _n);
m = U.size();
graph.resize(n);
tree.resize(n);
backedge.resize(n);
bl.assign(n, 0);
depth.resize(n);
royal.assign(m, 0);
DD.resize(n, {-1, -1});
for(int i = 0; i < m; i++){
graph[U[i]].pb({V[i], i});
graph[V[i]].pb({U[i], i});
}
dfs0(0);
X = count_common_roads(cur);
dfs(0, -1);
vector<int> ans;
for(int i = 0; i < m; i++) if(royal[i]) ans.pb(i);
return ans;
}
