#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;
DSU(int n = 0) : n(n), par(n, -1) {}
int find(int v) {return par[v] == -1 ? v :par[v] = find(par[v]);}
void unite(int a, int b) {if (find(a) != find(b)) par[find(b)] = find(a);}
};
int n, m, timer = 0;
vvi G; vi x, y, is_bridge, tin, low, par, back;
bool is_tree_edge(int e) {return par[x[e]] == e || par[y[e]] == e;}
void dfs(int u, int p) {
tin[u] = low[u] = timer++;
for (auto e : G[u]) {
if (e == p) continue;
int v = u^x[e]^y[e];
if (tin[v] != -1) {
if (tin[v] < low[u]) low[u] = tin[v], back[u] = e;
} else {
par[v] = e;
dfs(v, e);
if (low[v] > tin[u]) is_bridge[e] = 1;
if (low[v] < low[u]) back[u] = e, low[u] = low[v];
}
}
}
vi cycle(int e) {
int u = par[x[e]] == e ? y[e] : x[e]; int v = u == x[e] ? y[e] : x[e];
vi ans(1, e);
int cur = v;
while (is_tree_edge(back[cur])) ans.push_back(back[cur]), cur = x[back[cur]]^y[back[cur]]^cur;
int be = back[cur], anc = tin[x[be]] < tin[y[be]] ? x[be] : y[be];
vi to_anc; cur = u;
while (cur != anc) to_anc.push_back(par[cur]), cur = x[par[cur]]^y[par[cur]]^cur;
reverse(to_anc.begin(), to_anc.end());
ans.push_back(be);
for (auto e: to_anc) ans.push_back(e);
return ans;
}
/*
golden set = spanning tree, royal set = specific spanning tree to find
if we can find a spanning tree where we know the status of every edge, then you can
test how many golden edges are in a subset by adding valid edges from the spanning tree, counting
the expected number of golden edges in the output and diffing it with the actual (obvious)
(my initial thing was looking for a tree with 0 edges, which is stupid, should have just looked for knowing)
this helps because we can either (slow) test each edge individually, OR (fast) binary search on all edges of
each node to find which ones are golden (works because every node has > 0 golden edges).
how to find? note that for a given cycle in the graph, you can try making a spanning tree missing exactly 1
of the edges in the cycle for each edge, and use the exact same edges other than that for the spanning tree.
if ans(edge1) > ans(edge2), then e1 is golden, e2 is not. ans(edge1) = ans(edge2) then we know they share the same status.
but how to figure out that status? if all edges in the cycle have the same value, then none of them can be good, otherwise
they would all appear in the spanning tree ⇒ cycle in the spanning tree --> contradiction
so if they dont all share, those with the lower value (removing them decreased num golden) are golden
if at least 1 node in the cycle is already identified, you just need to query the cycle missing either E or F(ound)
so you would want to minimise the total number of distinct edges amongst all cycles you use. one method of doing this
is to consider the dfs tree of the graph (arbitrary root), + one back edge for every node with a back edge. there are at
most 2N edges in this reduced graph, and as the dfs tree is a spanning tree, it means that done this way we have a construction
that determines the answer for every edge of an arbitrary initial spanning tree in 2N queries, and then can do the binary search method
*/
vi find_roads(int N, vi U, vi V) {
n = N; m = U.size();
G.assign(n, vi()); x = U; y = V; is_bridge.assign(m, 0),
par.assign(n, -1), back.assign(n, -1); tin.assign(n, -1); low.assign(n, -1);
for (int i = 0; i < m; i++) G[x[i]].push_back(i), G[y[i]].push_back(i);
dfs(0, -1);
vi checked(m, 0), royal = is_bridge;
vi spanning_tree; for (int i = 1; i < n; i++) spanning_tree.push_back(par[i]);
auto test_subset = [&](vi s, bool sub = false) {
auto dsu = DSU(n);
for (auto e : s) dsu.unite(x[e], y[e]);
int expected = 0; for (auto e : spanning_tree) {
if (dsu.find(x[e]) == dsu.find(y[e])) continue;
dsu.unite(x[e], y[e]); s.push_back(e); if (royal[e]) expected++;
}
return count_common_roads(s) - (sub ? expected : 0);
};
for (auto i : spanning_tree) {
if (checked[i]) continue;
if (is_bridge[i]) continue;
vi c = cycle(i);
int found = -1; for (auto e : c) if (checked[e]) found = e;
if (found == -1) {
vi R(c.size()); int lo = INT_MAX, hi = INT_MIN;
for (int i = 0; i < c.size(); i++) {
vi c2; for (int j = 0; j < c.size(); j++) if (j != i) c2.push_back(c[j]);
R[i] = test_subset(c2); lo = min(lo, R[i]), hi = max(hi, R[i]);
}
for (int i = 0; i < c.size(); i++) {
checked[c[i]] = 1;
royal[c[i]] = R[i] != hi;
}
} else {
vi s1, s2;
for (auto e : c) {
if (e != found) s1.push_back(e);
if (e != i) s2.push_back(e);
}
int r1 = test_subset(s1), r2 = test_subset(s2);
if (r1 == r2) royal[i] = royal[found];
else if (r2 != r1) royal[i] = 1-royal[found];
checked[i] = checked[found] = 1;
}
}
for (int i = 0; i < n; i++) {
bool found = true;
while (found) {
found = false;
vi g2; for (auto e : G[i]) if (!checked[e]) g2.push_back(e);
swap(G[i], g2);
int lo = 1, hi = G[i].size()+1;
while (lo < hi) {
int mid = lo + (hi-lo) / 2;
vi subs; for (int j = 0; j < mid; j++) subs.push_back(G[i][j]);
if (test_subset(subs, true) > 0) hi = mid, found = true;
else lo = mid + 1;
}
if (found) {
for (int j = 0; j < lo; j++) checked[G[i][j]] = 1;
royal[G[i][lo-1]] = 1;
} else {
for (int j = 0; j < G[i].size(); j++) checked[G[i][j]] = 1;
}
}
}
vi ans; for (int i = 0; i < m; i++) if (royal[i]) ans.push_back(i);
return ans;
}
