#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 :par[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];
}
}
};
vvi G; vi X, Y;
int timer = 0;
vi tin, low, par, back;
vi is_bridge, is_articulation_point;
vvi bccs; vi estack, my_bcc;
void dfs(int u, int p) {
par[u] = p;
tin[u] = low[u] = timer++;
int children = 0;
for (auto e : G[u]) {
if (e == p) continue;
int v = X[e] == u ? Y[e] : X[e];
if (tin[v] == -1) {
estack.push_back(e);
dfs(v, e);
if (low[v] > tin[u]) {
is_bridge[e] = 1;
}
if (low[v] >= tin[u]) {
if (p != -1) is_articulation_point[u] = 1;
vi cmp; while (!estack.empty() && estack.back() != e) cmp.push_back(estack.back()), estack.pop_back();
if (!estack.empty()) cmp.push_back(e), estack.pop_back();
for (auto e : cmp) my_bcc[e] = bccs.size();
bccs.push_back(cmp);
}
if (low[v] < low[u]) back[u] = e, low[u] = low[v];
children++;
} else if (tin[v] < tin[u]) { // back edge
estack.push_back(e);
if (tin[v] < low[u]) back[u] = e, low[u] = tin[v];
}
}
if (p == -1 && children > 1) is_articulation_point[u] = 1;
}
int other_end(int e, int u) {
return X[e] == u ? Y[e] : X[e];
}
bool is_tree_edge(int e) {
return par[X[e]] == e || par[Y[e]] == e;
}
vi find_cycle(int e) {
if (!is_tree_edge(e)) {
int a = X[e], b = Y[e];
int anc = tin[a] < tin[b] ? a : b;
int desc = anc == a ? b : a;
vi cyc = {e};
int cur = desc;
while (cur != anc) {
int pe = par[cur];
cyc.push_back(pe);
cur = other_end(pe, cur);
}
return cyc;
}
int c = (par[X[e]] == e ? X[e] : Y[e]);
int p = other_end(e, c);
vi down;
int cur = c;
while (true) {
int be = back[cur];
if (is_tree_edge(be)) {
int nxt = (par[X[be]] == be ? X[be] : Y[be]);
down.push_back(be);
cur = nxt;
} else {
int z = cur;
int a = (tin[X[be]] < tin[Y[be]] ? X[be] : Y[be]);
vi up;
int x = p;
while (x != a) {
int pe = par[x];
up.push_back(pe);
x = other_end(pe, x);
}
reverse(up.begin(), up.end());
vi cyc;
cyc.push_back(e);
for (int x : down) cyc.push_back(x);
cyc.push_back(be);
for (int x : up) cyc.push_back(x);
return cyc;
}
}
}
vi find_roads(int n, vi u, vi v) {
int m = u.size();
X = u; Y = v;
map<pair<int, int>, int> rebase;
G.assign(n, vi()); 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; tin.assign(n, -1), low.assign(n, -1); is_bridge.assign(m, 0); is_articulation_point.assign(n, 0);
my_bcc.assign(m, -1); par.assign(n, -1); back.assign(n, -1);
dfs(0, -1);
for (int i = 0; i < m; i++) if (is_bridge[i]) edges.push_back(i);
int bcc_cnt = bccs.size();
vector<int> processed(bcc_cnt, 0);
vi checked_royal(m, 0), royalc(m, 0);
cout << "hi\n";
auto is_royal = [&](int e) {
if (is_bridge[e]) return royalc[e] = 1;
if (checked_royal[e]) return royalc[e];
auto dsu = DSU(n);
vi pe = find_cycle(e); for (auto e : pe) dsu.unite(u[e], v[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);
int found = -1;
for (int i = 0; i < pe.size(); i++) {
if (checked_royal[pe[i]]) found = i;
}
if (found == -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";
for (int i = 0; i < pe.size(); i++) {
royalc[pe[i]] = R[i] != hi;
checked_royal[pe[i]] = 1;
}
} else {
vi c = cc; for (int j = 0; j < pe.size(); j++) if (found != j) c.push_back(pe[j]);
int x1 = count_common_roads(c);
vi c2 = cc; for (int j = 1; j < pe.size(); j++) c2.push_back(pe[j]);
int x2 = count_common_roads(c2);
if (x1 == x2) royalc[e] = royalc[pe[found]];
else royalc[e] = x2 < x1;
}
checked_royal[e] = 1;
return royalc[e];
};
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 < n; i++) {
bool found = true;
while (found) {
found = false;
int lo = 1, hi = G[i].size()+1;
while (lo < hi) {
int mid = lo + (hi-lo)/2;
auto dsu2 = DSU(n);
int exp = 0;
vi cc; for (int j = 0; j < mid; j++) cc.push_back(G[i][j]), dsu2.unite(u[G[i][j]], v[G[i][j]]), exp += royalc[G[i][j]];
for (int j = 0; j < n-1; j++) {
if (dsu2.find(u[mc[j]]) == dsu2.find(v[mc[j]])) continue;
exp += royal[j]; cc.push_back(mc[j]); dsu2.unite(u[mc[j]], v[mc[j]]);
}
int v = count_common_roads(cc);
cout << "testing the set "; for (auto e : cc) cout << e << " "; cout << "expecting " << exp << " got " << v << "\n";
if (v == exp) lo = mid + 1;
else hi = mid, found = true;
}
if (found) {
cout << "hallo\n";
int e = G[i][lo-1];
royalc[G[i][lo-1]] = 1;
ans.push_back(e);
}
}
}
ans.clear(); for (int i =0 ; i < m; i++) if (royalc[i])ans.push_back(i);
for (auto e : ans) cout << e << " "; cout << "\n";
return ans;
}
