#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int n;
vi pai;
vector<vector<pii>> tree;
void reset_dsu() {
pai.resize(n);
for(int i = 0; i < n; i++) pai[i] = i;
}
int find(int x) {
if(x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
pai[find(x)] = pai[find(y)];
}
vi cam, visited;
bool dfs(int x, int y) {
visited[x] = 1;
if(x == y) return 1;
for(auto [viz, id] : tree[x]) {
if(visited[viz]) continue;
cam.pb(id);
if(dfs(viz, y)) return 1;
cam.pop_back();
}
return 0;
}
void call_dfs(int x, int y) {
cam.clear();
visited.clear();
visited.resize(n);
dfs(x, y);
}
vi find_roads(int N, vi u, vi v) {
n = N;
int m = sz(u);
tree.resize(n);
reset_dsu();
vi tree_set, state(m, -1), pos(m, -1);
for(int i = 0; i < m; i++) {
if(find(u[i]) == find(v[i])) continue;
tree[u[i]].pb({v[i], i});
tree[v[i]].pb({u[i], i});
join(u[i], v[i]);
pos[i] = sz(tree_set);
tree_set.pb(i);
}
int tree_qtd = count_common_roads(tree_set);
for(int i = 0; i < m; i++) {
if(pos[i] != -1) continue;
call_dfs(u[i], v[i]);
vi rsp;
int k = -1, max_rsp = tree_qtd;
for(int j : cam) {
if(state[j] != -1) {
rsp.pb(-1);
k = j;
continue;
}
tree_set[pos[j]] = i;
int new_qtd = count_common_roads(tree_set);
rsp.pb(new_qtd);
tree_set[pos[j]] = j;
max_rsp = max(max_rsp, new_qtd);
}
if(k != -1) { // por causa dessa parte fica Q ~ n(n-1)/2
tree_set[pos[k]] = i;
int new_qtd = count_common_roads(tree_set);
tree_set[pos[k]] = k;
max_rsp = new_qtd + state[k];
}
for(int j = 0; j < sz(cam); j++)
if(state[cam[j]] == -1) state[cam[j]] = rsp[j] != max_rsp;
state[i] = tree_qtd != max_rsp;
}
vi ans;
for(int i = 0; i < m; i++)
if(state[i]) ans.pb(i);
return ans;
}
