#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define cout cerr
struct DSU {
int n; vector<int> par, sz, U, P;
DSU(int n = 0) : n(n), par(n, -1), sz(n, 1) {}
int find(int v) {return par[v] == -1 ? v :find(par[v]);}
void unite(int a, int b) {
a =find(a); b = find(b);
if (a != b) {
if (sz[a] < sz[b]) swap(a, b);
U.push_back(b); P.push_back(par[b]);
par[b] = a; sz[a] += sz[b];
}
}
void rollback() {
if (U.empty()) return;
sz[par[U.back()]] -= sz[U.back()];
par[U.back()] = P.back();
U.pop_back(); P.pop_back();
}
};
int timer = 0;
vi X, Y;
vi lowdet;
void dfs(int u, int p, vvi &G, vi &tin, vi &low, set<int> &bridges, set<int> &aps) {
tin[u] = low[u] = timer++;
int children = 0;
for (auto e : G[u]) {
int v = X[e] == u ? Y[e] : X[e];
if (v == p) continue;
if (tin[v] != -1) {
low[u] = min(low[u], tin[v]);
if (low[u] == tin[v]) lowdet[u] = e;
continue;
}
dfs(v, u, G, tin, low, bridges, aps);
if (low[v] > tin[u]) bridges.insert(e);
if (low[v] >= tin[u] && u != p) aps.insert(u);
low[u] = min(low[u], low[v]);
if (low[u] == low[v]) lowdet[u] = e;
children++;
}
if (u==p && children > 1) aps.insert(u);
}
/*
the construction used was a line connected to a hub
how about a dfs rooted arbitrarily
first a spanning tree is made excluding the root (choose a non-articulation point, so that graph is still connected w/o it)
and then each edge of the root is tested to find whether or not it is part of the desired spanning tree
then recurse to a child. binary search to find which children when removed and connected us have more in st than expected
*/
vi find_roads(int n, vi u, vi v) {
int m = u.size();
X = u; Y = v; lowdet.assign(n, -1);
map<pair<int, int>, int> rebase;
vvi G(n); for (int i = 0; i < m; i++) G[u[i]].push_back(i), G[v[i]].push_back(i), rebase[{u[i], v[i]}] = i, rebase[{v[i], u[i]}] = i;
deque<int> edges; vi tin(n, -1), low(n, -1);
set<int> articulation_points, bridges;
dfs(0, 0, G, tin, low, bridges, articulation_points);
for (auto b : bridges) edges.push_back(b);
auto is_royal = [&](int e) {
if (bridges.count(e)) return true;
int S = u[e], T = v[e];
set<int> path; vi par(n, -1);
queue<int> q; q.push(S);
par[S] = n;
while (!q.empty()) {
int x = q.front(); q.pop();
for (auto e2 : G[x]) {
if (e2 == e) continue;
int y = u[e2] == x ? v[e2] : u[e2];
if (par[y] != -1) continue;
par[y] = e2;
q.push(y);
}
}
for (auto x : par) cout << x << " "; cout << "\n";
int cur = T;
while (par[cur] != n) {
path.insert(par[cur]);
cur = u[par[cur]] == cur ? v[par[cur]] : u[par[cur]];
}
auto dsu = DSU(n); vi pe(1, e);
for (auto e : path) dsu.unite(u[e], v[e]), pe.push_back(e);
vi cc; for (int i = 0; i < m; i++) {
if (dsu.find(u[i]) != dsu.find(v[i])) dsu.unite(u[i], v[i]), cc.push_back(i);
}
vi R(pe.size(), -1);
for (int i = 0; i < pe.size(); i++) {
vi c = cc; for (int j = 0; j < pe.size(); j++) if (i != j) c.push_back(pe[j]);
R[i] = count_common_roads(c);
}
int lo = *min_element(R.begin(), R.end()), hi = *max_element(R.begin(), R.end());
cout << "the cycle of edge " << e << " was"; for (auto e : pe); cout << " " << e; cout << "\n";
return R[0] != hi;
};
vi mc, ans, royal(n-1, 0); // hammer
set<int> used;
auto dsu = DSU(n);
for (int i = 0; i < m; i++) {
if (dsu.find(u[i]) == dsu.find(v[i])) continue;
dsu.unite(u[i], v[i]); mc.push_back(i);
royal[mc.size()-1] = is_royal(i);
if (royal[mc.size()-1]) ans.push_back(i);
used.insert(i);
}
cout << "chosen: "; for (auto e : mc) cout << e << " "; cout << "\n";
cout << "royal chosen: "; for (int i = 0; i < n-1; i++) if (royal[i]) cout << mc[i] << " "; cout << "\n";
for (int i = 0; i < m; i++) {
if (used.count(i)) continue;
vi c2(1, i);
auto dsu2 = DSU(n);
dsu2.unite(u[i], v[i]);
int expected = 0;
for (int j = 0; j < n-1; j++) {
int x = u[mc[j]], y = v[mc[j]];
if (dsu2.find(x) == dsu2.find(y)) continue;
if (royal[j]) expected++;
dsu2.unite(x, y);
c2.push_back(mc[j]);
}
if (count_common_roads(c2) != expected) ans.push_back(i);
}
for (auto e : ans) cout << e << " "; cout << "\n";
return ans;
// int B = edges.size();
// set<int> bad, good;
// for (auto e : edges) good.insert(e);
// auto dsu = DSU(n);
// vi mc; // hammer;
// for (int i = 1; i < n-1; i++) {
// mc.push_back(rebase[{i, i+1}]);
// }
// vi R(1, -1);
// for (int i = 1; i < n; i++) {
// mc.push_back(rebase[{0, i}]);
// R.push_back(count_common_roads(mc));
// mc.pop_back();
// }
// mc.clear();
// int least = *min_element(R.begin() + 1, R.end());
// int most = *max_element(R.begin() + 1, R.end());
// for (int i = 1; i < n; i++) {
// if (R[i] == most) mc.push_back(rebase[{0, i}]), good.insert(rebase[{0, i}]);
// else {
// bad.insert(i);
// // cout << "0->" << i << " is not good\n";
// }
// }
// for (int u = 1; u < n-1; u++) {
// bool found = true;
// while (found) {
// found = false;
// int lo = 1, hi = n;
// while (lo < hi) {
// int mid = lo + (hi-lo)/2;
// vi ch; ch.push_back(rebase[{0, u}]);
// for (int i = 1; i < n; i++) {
// if (i == u) continue;
// if (i <= mid) ch.push_back(rebase[{u, i}]);
// else ch.push_back(rebase[{0, i}]);
// }
// int expected = 0; for (auto e : ch) if (good.count(e)) expected++;
// // cout << "trying set "; for (auto e : ch) cout << e << " "; cout << "expecting " << expected << "\n";
// int f = count_common_roads(ch);
// // cout << "got " << f << "\n";
// if (expected == f) lo = mid + 1;
// else hi = mid, found = true;
// }
// // if (!found) break;
// if (found) {
// // cout << "found " << u << "->" << lo << "\n";
// mc.push_back(rebase[{u, lo}]);
// good.insert(rebase[{u, lo}]);
// }
// }
// }
// // cout << "final answer "; for (auto e : mc) cout << e << " "; cout << "\n";
// return mc;
// bitset<125'000> avail; for (int i = 0; i < m; i++) avail[i] = 1;
// for (auto e : edges) avail[e] = 0;
// auto add = [&](int x) {
// if (x<m && avail[x]) {
// edges.push_back(x);
// avail[x] = 0;
// }
// dsu = DSU(n); mc.clear();
// for (auto e : edges) dsu.unite(u[e], v[e]), mc.push_back(e);
// for (int i = 0; i < m; i++) {
// if (dsu.find(u[i]) == dsu.find(v[i])) continue;
// dsu.unite(u[i], v[i]); mc.push_back(i);
// }
// };
// add(m);
// while (edges.size() < n-1) {
// int cnt = count_common_roads(mc);
// int x = mc.back(); mc.pop_back();
// dsu.rollback();
// vi g, e, s;
// for (int i = avail._Find_first(); i < m; i = avail._Find_next(i)) {
// if (dsu.find(u[i]) == dsu.find(v[i])) continue;
// dsu.unite(u[i], v[i]); mc.push_back(i);
// int c2 = count_common_roads(mc);
// dsu.rollback(); mc.pop_back();
// if (c2 > cnt) {
// g.push_back(i);
// } else if (c2 == cnt) {
// e.push_back(i);
// } else {
// s.push_back(i);
// }
// }
// if (g.size() == 0) {
// for (auto v : e) add(v);
// } else {
// for (auto v : g) add(v);
// }
// for (auto v : g) avail[v] = 0;
// for (auto v : e) avail[v] = 0;
// for (auto v : s) avail[v] = 0;
// }
// vi r; for (auto &e : edges) r.push_back(e);
// return r;
}
