#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> par;
dsu(int n) {
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int holvan(int u) {
return par[u] == u ? u : (par[u] = holvan(par[u]));
}
bool unio(int u, int v) {
u = holvan(u); v = holvan(v);
if (u == v) return 0;
par[u] = v;
return 1;
}
};
vector<int> find_roads(int n, vector<int> e1, vector<int> e2) {
int m = e1.size();
vector<vector<pair<int, int>>> g(n), g2(n);
vector<int> dfs_tree;
vector<int> col(n);
vector<bool> vis(n);
for (int i = 0; i < m; i++) {
g[e1[i]].emplace_back(e2[i], i);
g[e2[i]].emplace_back(e1[i], i);
}
auto dfs = [&](auto &&self, int u) -> void {
vis[u] = 1;
for (auto [v, idx] : g[u]) {
if (vis[v]) continue;
dfs_tree.emplace_back(idx);
g2[u].emplace_back(v, idx);
g2[v].emplace_back(u, idx);
self(self, v);
}
};
dfs(dfs, 0);
auto dfs2 = [&](auto &&self, int u, int block, int c) -> void {
col[u] = c;
for (auto [v, idx] : g2[u]) {
if (col[v] || v == block) continue;
self(self, v, block, c);
}
};
int asked = 0;
int dfs_tree_cnt = count_common_roads(dfs_tree);
asked++;
vector<int> label(m, -1);
for (int idx : dfs_tree) {
int u = e1[idx];
int v = e2[idx];
fill(col.begin(), col.end(), 0);
dfs2(dfs2, u, v, 1);
dfs2(dfs2, v, u, 2);
vector<int> replacements;
for (int i = 0; i < m; i++) {
if (i == idx) continue;
if (col[e1[i]] != col[e2[i]]) {
replacements.emplace_back(i);
}
}
if (replacements.empty()) {
label[idx] = 1;
continue;
}
vector<int> s;
for (int x : dfs_tree) {
if (x != idx) s.emplace_back(x);
}
bool ok = false;
for (int x : replacements) {
if (label[x] != -1) {
s.emplace_back(x);
ok = true;
assert(asked <= 8000);
int cnt = count_common_roads(s);
asked++;
int should_be = dfs_tree_cnt + (label[x] == 1);
label[idx] = should_be != cnt;
break;
}
}
if (ok) continue;
label[idx] = 1;
int it = 0;
vector<int> checked;
for (int x : replacements) {
it++;
s.emplace_back(x);
assert(asked <= 8000);
int cnt = count_common_roads(s);
asked++;
if (cnt > dfs_tree_cnt) {
label[idx] = 0;
break;
}
if (cnt < dfs_tree_cnt) {
break;
}
checked.emplace_back(x);
s.pop_back();
}
for (int x : checked) {
label[x] = label[idx];
}
}
vector<int> todo;
vector<int> vis2(n), vis3(m);
auto gen_todo = [&](auto &&self, int u) -> void {
vis2[u] = 1;
for (auto [v, idx] : g[u]) {
if (label[idx] != -1 || vis2[v] || vis3[idx]) continue;
vis3[idx] = 1;
todo.emplace_back(idx);
self(self, v);
}
};
for (int it = 0; it < 500; it++) {
fill(vis2.begin(), vis2.end(), 0);
for (int i = 0; i < n; i++) {
if (!vis2[i]) gen_todo(gen_todo, i);
}
}
auto f = [&](int l, int r) {
dsu ds(n);
vector<int> roads;
for (int i = l; i < r; i++) {
ds.unio(e1[todo[i]], e2[todo[i]]);
roads.emplace_back(todo[i]);
}
int should_be = dfs_tree_cnt;
for (int idx : dfs_tree) {
if (!ds.unio(e1[idx], e2[idx])) {
should_be -= label[idx];
} else {
roads.emplace_back(idx);
}
}
int cnt = count_common_roads(roads);
asked++;
return cnt > should_be;
};
int nxt = 0;
while (nxt < todo.size()) {
int last = nxt;
dsu ds(n);
while (last < todo.size()) {
if (ds.unio(e1[todo[last]], e2[todo[last]])) {
last++;
} else {
break;
}
}
if (!f(nxt, last)) {
nxt = last;
continue;
}
int lo = nxt, hi = last-1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (!f(nxt, mid)) lo = mid;
else hi = mid-1;
}
nxt = lo+1;
label[todo[lo]] = 1;
}
vector<int> ans;
for (int i = 0; i < m; i++) {
if (label[i] == 1) ans.emplace_back(i);
}
return ans;
}
