#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, u, v;
vector<vector<pii>> tree;
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 make_tree(vi &edges) {
for(int i = 0; i < n; i++) pai[i] = i;
vi T;
for(int i : edges) {
if(find(u[i]) == find(v[i])) continue;
join(u[i], v[i]);
T.pb(i);
}
return T;
}
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 operator + (vi &a, vi &b) {
vi c = a;
for(auto it : b) c.pb(it);
return c;
}
vi find_roads(int N, vi U, vi V) {
n = N; u = U; v = V;
int m = sz(u);
tree.resize(n);
pai.resize(n);
vi ord(m), tree_set, state(m, -1), pos(m, -1);
for(int i = 0; i < m; i++) ord[i] = i;
tree_set = make_tree(ord);
for(int j = 0, i; j < sz(tree_set); j++) {
i = tree_set[j];
pos[i] = j;
tree[u[i]].pb({v[i], i});
tree[v[i]].pb({u[i], 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, calls = 0, 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); calls++;
rsp.pb(new_qtd);
tree_set[pos[j]] = j;
max_rsp = max(max_rsp, new_qtd);
}
if(calls == 0) continue;
if(k != -1) {
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;
}
vector<vi> edges(n);
for(int i = 0; i < m; i++) {
edges[u[i]].pb(i);
edges[v[i]].pb(i);
if(pos[i] != -1) state[i] = !!state[i];
}
for(int no = 0; no < n; no++) {
vi no_set, T;
while(1) {
no_set.clear();
for(int i : edges[no])
if(state[i] == -1) no_set.pb(i);
if(no_set.empty()) break;
T = no_set + tree_set;
T = make_tree(T);
int no_qtd = count_common_roads(T), cnt = 0;
for(auto it : T) if(pos[it] != -1) cnt += state[it];
if(cnt == no_qtd) break;
int l = 0, r = sz(no_set)-1;
while(l < r) {
int mid = (l+r)/2;
T.clear();
for(int i = l; i <= mid; i++) T.pb(no_set[i]);
T = T + tree_set;
T = make_tree(T);
int no_qtd = count_common_roads(T), cnt = 0;
for(auto it : T) if(pos[it] != -1) cnt += state[it];
if(cnt == no_qtd) l = mid+1;
else r = mid;
}
for(int i = 0; i < l; i++) state[no_set[i]] = 0;
state[no_set[l]] = 1;
}
}
vi ans;
for(int i = 0; i < m; i++)
if(state[i] == 1) ans.pb(i);
return ans;
}
