#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int>> edges;
vector<vector<pair<int, int>>> g1;
vector<set<pair<int, int>>> g;
vector<int> good;
void calc(int i){
int start = edges[i].first, goal = edges[i].second;
queue<int> q;
q.push(start);
vector<bool> vis(n);
vis[start] = true;
vector<pair<int, int>> last(n);
while(!q.empty()){
int u = q.front();
q.pop();
for(auto [v, ind] : g[u]){
if(ind == i) continue;
if(!vis[v]){
vis[v] = true;
q.push(v);
last[v] = {u, ind};
}
}
}
if(!vis[goal]){ // bridge
good[i] = true;
return;
}
vector<int> cycle;
vector<int> inCycle(m);
int u = goal;
while(u != start){
inCycle[last[u].second] = true;
cycle.push_back(last[u].second);
u = last[u].first;
}
inCycle[i] = true;
cycle.push_back(i);
vector<int> forest;
for(u = 0; u < n; u++){
if(u != start){
int e = last[u].second;
if(!inCycle[e]) forest.push_back(e);
}
}
int c = (int)cycle.size();
vector<int> ans(c);
for(int j = 0; j < c; j++){
if(good[cycle[j]] == 1) ans[j] = -1;
else{
vector<int> v;
for(int k = 0; k < c; k++){
if(k != j) v.push_back(cycle[k]);
}
for(int e : forest) v.push_back(e);
ans[j] = count_common_roads(v);
}
}
for(int j = 0; j < c; j++){
int ma = 0;
for(int k = 0; k < c; k++){
if(j != k) ma = max(ma, ans[k]);
}
good[cycle[j]] = ma > ans[j];
if(good[cycle[j]] == 0){
int a = edges[cycle[j]].first, b = edges[cycle[j]].second;
g[a].erase({b, cycle[j]});
g[b].erase({a, cycle[j]});
}
}
}
mt19937 mt(1243234);
vector<bool> vis;
vector<int> path;
void dfs(int u){
vis[u] = true;
shuffle(g1[u].begin(), g1[u].end(), mt);
for(auto [v, ind] : g1[u]){
if(vis[v] || good[ind] == 0) continue;
dfs(v);
path.push_back(ind);
}
}
vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
n = n_;
m = (int)u.size();
g1.resize(n);
for(int i = 0; i < m; i++){
edges.emplace_back(u[i], v[i]);
g1[u[i]].emplace_back(v[i], i);
g1[v[i]].emplace_back(u[i], i);
}
good.resize(m, -1);
for(int it = 0; it < 500; it++){
path.clear();
vis.assign(n, false);
dfs(0);
if((int)path.size() != n-1) break;
if(count_common_roads(path) == 0){
for(int e : path) good[e] = 0;
}
}
g.resize(n);
for(int a = 0; a < n; a++){
for(auto [b, ind] : g1[a]){
if(good[ind] != 0) g[a].emplace(b, ind);
}
}
for(int i = 0; i < m; i++){
if(good[i] == -1){
calc(i);
}
}
vector<int> r;
for(int i = 0; i < m; i++) if(good[i] == 1) r.push_back(i);
return r;
}
