#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;
void dfs(int u, int p, vvi &G, vi &tin, vi &low, deque<int> &bridges) {
tin[u] = low[u] = timer++;
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]);
continue;
}
dfs(v, u, G, tin, low, bridges);
if (low[v] > tin[u]) bridges.push_back(e);
low[u] = min(low[u], low[v]);
}
}
vi find_roads(int n, vi u, vi v) {
int m = u.size();
X = u; Y = v;
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);
dfs(0, 0, G, tin, low, edges);
int B = edges.size();
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());
set<int> bad;
for (int i = 1; i < n; i++) {
if (R[i] == most) mc.push_back(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 = u, hi = n;
while (lo < hi) {
int mid = lo + (hi-lo)/2;
int expected = bad.count(u) ? 0 : 1;
vi ch;
ch.push_back(rebase[{0, u}]);
for (int i = 1; i <= mid; i++) {
if (i == u) continue;
ch.push_back(rebase[{u, i}]);
}
for (int i = mid+1; i < n; i++) {
if (i == u) continue;
ch.push_back(rebase[{0, i}]);
if (!bad.count(i)) expected++;
}
int f = count_common_roads(ch);
// cout << "tried set "; for (auto e : ch) cout << e << " "; cout << "expecting " << expected << " 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}]);
}
// }
}
// 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;
}
