#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
struct Edge {
int from;
int to;
int cost;
int id;
Edge(){};
Edge(int _from, int _to, int _cost, int _id) : from(_from), to(_to), cost(_cost), id(_id){};
};
struct graph {
int n;
vector<vector<int>> g;
vector<Edge> ed;
vector<bool> was;
graph(int _n) {
n = _n;
g.resize(n);
was.resize(n);
}
void add(int u, int v, int cost = 0) {
g[u].push_back(ed.size());
ed.emplace_back(u, v, cost, ed.size());
g[v].push_back(ed.size());
ed.emplace_back(v, u, -cost, ed.size());
}
void init_dfs() {
fill(was.begin(), was.end(), false);
}
template<typename E, typename F, typename G>
void _dp_dfs(int u, E&& bc, F&& fc, G&& gc) {
was[u] = true;
for(auto &e : g[u]) {
int v = ed[e].to;
if (was[v]) {
bc(u, v, ed[e]);
continue;
}
fc(u, v, ed[e]);
_dp_dfs(v, bc, fc, gc);
gc(u, v, ed[e]);
}
}
const vector<int>& operator[](int u){
return g[u];
}
};
vector<int> find_roads(int n, vector<int> n1, vector<int> n2) {
int m = n1.size();
graph gr(n);
for (int i = 0; i < m; i++) {
gr.add(n1[i], n2[i]);
}
vector<int> cost(m, -2);
graph edges(m);
vector<int> par(n, -1);
vector<int> dep(n);
vector<int> highest(n, -1);
gr._dp_dfs(0,
[&](int u, int v, Edge e) {
if (dep[v] == dep[u] - 1) {
return;
}
if (highest[u] == -1 || dep[gr.ed[highest[u]].to] > dep[v]) {
highest[u] = e.id;
}
},
[&](int u, int v, Edge e) {
par[v] = e.id ^ 1;
dep[v] = dep[u] + 1;
},
[&](int u, int v, Edge e) {
int eu = highest[u], pu = eu == -1 ? u : gr.ed[eu].to;
int ev = highest[v], pv = ev == -1 ? v : gr.ed[ev].to;
if (dep[pu] > dep[pv]) {
highest[u] = ev;
}
}
);
set<int> tree;
for (int i = 1; i < n; i++) {
tree.insert(par[i] >> 1);
}
auto calc = [&](set<int> ed) {
vector<int> que;
for (int i : ed) que.push_back(i);
return count_common_roads(que);
};
int sum = calc(tree);
auto diff = [&](int ev, int eu) {
tree.erase(eu);
tree.insert(ev);
int p = calc(tree);
tree.erase(ev);
tree.insert(eu);
return p - sum;
};
for (int v = 1; v < n; v++) {
int pv = par[v];
int u = gr.ed[pv].to;
int pu = par[u];
int w = highest[v] != -1 ? gr.ed[highest[v]].to : v;
if (dep[w] < dep[v]) {
int d = diff(highest[v] >> 1, pv >> 1);
edges.add(pv >> 1, highest[v] >> 1, d);
}
if (dep[w] < dep[u]) {
int d = diff(highest[v] >> 1, pu >> 1);
edges.add(pu >> 1, highest[v] >> 1, d);
}
}
for (int e : tree) {
if (cost[e] != -2) continue;
if (edges[e].empty()) {
cost[e] = 1;
} else {
vector<int> que = {e};
edges._dp_dfs(e,
[&](int u, int v, Edge E){},
[&](int u, int v, Edge E){
cost[v] = cost[u] + E.cost;
que.push_back(v);
},
[&](int u, int v, Edge E){}
);
int mn = INT_MAX;
for (int i : que) mn = min(mn, cost[i]);
for (int i : que) {
cost[i] -= mn;
assert(0 <= cost[i] && cost[i] <= 1);
}
}
}
auto calc_sum = [&](vector<int> forest) {
dsu d(n);
for (int e : forest) {
e <<= 1;
int u = gr.ed[e].from, v = gr.ed[e].to;
d.unite(u, v);
}
int calced = 0;
for (int e : tree) {
e <<= 1;
int u = gr.ed[e].from, v = gr.ed[e].to;
if (d.unite(u, v)) {
calced += cost[e >> 1];
forest.push_back(e >> 1);
}
}
return count_common_roads(forest) - calced;
};
function<void(vector<int>, int)> solve = [&](vector<int> Eds, int Sum) {
if (Sum == 0) {
for (int e : Eds) {
cost[e] = 0;
}
return;
}
if (Sum == (int) Eds.size()) {
for (int e : Eds) {
cost[e] = 1;
}
return;
}
int L = 0, R = Eds.size(), Mid = (L + R) >> 1;
vector<int> Leds, Reds;
for (int i = 0; i < (int) Eds.size(); i++) {
if (i < Mid) Leds.push_back(Eds[i]);
else Reds.push_back(Eds[i]);
}
int Lsum = calc_sum(Leds), Rsum = Sum - Lsum;
solve(Leds, Lsum);
solve(Reds, Rsum);
};
int Left = 0;
for (int i = 0; i < m; i++) Left += cost[i] == -2;
while (Left) {
dsu d(n);
vector<int> Eds;
for (int e = 0; e < m; e++) {
if (cost[e] != -2) continue;
int u = gr.ed[e << 1].from, v = gr.ed[e << 1].to;
if (d.unite(u, v)) Eds.push_back(e);
}
assert(Eds.size());
solve(Eds, calc_sum(Eds));
Left -= Eds.size();
}
vector<int> ret;
for (int e = 0; e < m; e++) {
assert(0 <= cost[e] && cost[e] <= 1);
if (cost[e] == 1) ret.push_back(e);
}
return ret;
}
