#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
// Extremely minimal DSU
struct DSU {
vector<int> par;
DSU(int n) { par.assign(n, -1); }
int find(int v) { return par[v] < 0 ? v : par[v] = find(par[v]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
par[b] = a;
return true;
}
};
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; ++i) {
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
vector<int> state(m, -1); // -1: unknown, 0: not royal, 1: royal
vector<bool> is_tree(m, false);
vector<int> depth(n, -1), par_node(n, -1), par_edge(n, -1), tree_edges;
// 1. Build a basic DFS Spanning Tree
auto dfs = [&](auto& self, int cur, int p, int d) -> void {
depth[cur] = d;
for (int id : adj[cur]) {
int nxt = u[id] ^ v[id] ^ cur; // Fast way to get the other endpoint
if (nxt == p) continue;
if (depth[nxt] == -1) {
is_tree[id] = true;
par_node[nxt] = cur;
par_edge[nxt] = id;
tree_edges.push_back(id);
self(self, nxt, cur, d + 1);
}
}
};
dfs(dfs, 0, -1, 0);
// 2. PHASE 1: Resolve all cycles formed by back-edges
for (int i = 0; i < m; ++i) {
if (is_tree[i]) continue; // Only process back-edges
// Find the simple path in the tree going up from descendant to ancestor
int curr = depth[u[i]] > depth[v[i]] ? u[i] : v[i];
int anc = depth[u[i]] > depth[v[i]] ? v[i] : u[i];
vector<int> cyc = {i};
while (curr != anc) {
cyc.push_back(par_edge[curr]);
curr = par_node[curr];
}
// Check if we need to query this cycle (do we have unknown edges?)
int known_idx = -1;
bool needs_query = false;
for (int j = 0; j < cyc.size(); ++j) {
if (state[cyc[j]] != -1) known_idx = j;
else needs_query = true;
}
if (!needs_query) continue;
// Query the spanning tree by swapping each cycle edge with the back-edge
vector<int> ans(cyc.size(), -1);
int mx = -1;
for (int j = 0; j < cyc.size(); ++j) {
if (known_idx != -1 && state[cyc[j]] != -1 && j != known_idx) continue;
vector<int> q;
for (int e : tree_edges) if (e != cyc[j]) q.push_back(e);
if (j > 0) q.push_back(i); // j == 0 is the back-edge itself
ans[j] = count_common_roads(q);
mx = max(mx, ans[j]);
}
// Deduce states based on the query results
for (int j = 0; j < cyc.size(); ++j) {
if (state[cyc[j]] != -1) continue;
if (known_idx == -1) {
state[cyc[j]] = (ans[j] != mx);
} else {
if (ans[j] == ans[known_idx]) state[cyc[j]] = state[cyc[known_idx]];
else if (ans[j] > ans[known_idx]) state[cyc[j]] = 0;
else state[cyc[j]] = 1;
}
}
}
// Any tree edge still unknown was never in a cycle (it's a bridge). Therefore, royal.
for (int e : tree_edges) if (state[e] == -1) state[e] = 1;
// 3. PHASE 2: Divide and Conquer the remaining graph
auto query_subset = [&](const vector<int>& subset) {
DSU dsu(n);
vector<int> q;
int known_royals = 0;
for (int e : subset) {
q.push_back(e);
dsu.unite(u[e], v[e]);
}
for (int e : tree_edges) { // Complete the tree using known tree edges
if (dsu.unite(u[e], v[e])) {
q.push_back(e);
known_royals += state[e];
}
}
return count_common_roads(q) - known_royals;
};
auto solve_star = [&](auto& self, vector<int> edges, int expected) -> void {
if (expected == 0) {
for (int e : edges) state[e] = 0; return;
}
if (expected == (int)edges.size()) {
for (int e : edges) state[e] = 1; return;
}
int mid = edges.size() / 2;
vector<int> L(edges.begin(), edges.begin() + mid);
vector<int> R(edges.begin() + mid, edges.end());
int left_count = query_subset(L);
self(self, L, left_count);
self(self, R, expected - left_count);
};
// Run the D&C on all unknown edges incident to each vertex
for (int i = 0; i < n; ++i) {
vector<int> unk;
for (int id : adj[i]) if (state[id] == -1) unk.push_back(id);
if (!unk.empty()) solve_star(solve_star, unk, query_subset(unk));
}
// 4. Compile answers
vector<int> royal_roads;
for (int i = 0; i < m; ++i) if (state[i] == 1) royal_roads.push_back(i);
return royal_roads;
}
