#include "simurgh.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 505;
int n, m;
int ad[mxN][mxN];
vector<int> g[mxN];
vector<pair<int, int>> edges;
struct DSU {
int n;
vector<int> par;
DSU(int _n) {
n = _n;
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int find(int u) {
return (u == par[u] ? u : find(par[u]));
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
par[u] = v;
return true;
}
};
int query(vector<int> r) {
return count_common_roads(r);
}
set<int> tree;
vector<int> nodes[mxN];
set<int> on;
int Myquery(vector<int> v) {
vector<int> r;
DSU dsu(n);
for (int i : v) {
auto [u, v] = edges[i];
r.push_back(i);
dsu.unite(u, v);
}
for (int i : on) {
auto [u, v] = edges[i];
if (dsu.unite(u, v)) r.push_back(i);
}
for (int i : tree) {
auto [u, v] = edges[i];
if (dsu.unite(u, v)) r.push_back(i);
}
return query(r);
}
int init;
int reduction(vector<int> v) {
vector<int> r;
DSU dsu(n);
for (int i : v) {
auto [u, v] = edges[i];
r.push_back(i);
dsu.unite(u, v);
}
int ans = 0;
for (int i : on) {
auto [u, v] = edges[i];
if (dsu.unite(u, v)) r.push_back(i);
else ans++;
}
for (int i : tree) {
auto [u, v] = edges[i];
if (dsu.unite(u, v)) r.push_back(i);
}
return ans;
}
vector<int> get(int u, int p) {
vector<int> ret = {u};
for (int v : g[u]) {
if (v == p) continue;
auto r = get(v, u);
for (int i : r) ret.push_back(i);
}
return ret;
}
int par[mxN];
void init_parent(int u, int p) {
for (int v : g[u]) {
if (v == p) continue;
par[v] = u;
init_parent(v, u);
}
}
void dfs(int u, int p) {
// debug("start", u, on);
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u);
}
// debug("after tree edge", u, on);
for (int v : g[u]) {
if (v == p) continue;
// for each node a in subtree of v, binary search to find edges to the left subtrees
for (int a : nodes[v]) {
vector<int> cur;
for (int b : nodes[u]) {
if (ad[a][b] != -1) cur.push_back(ad[a][b]);
}
int L = 0;
while (L < cur.size()) {
int val = Myquery({});
int lo = L, hi = cur.size();
while (lo < hi) {
int mid = (lo + hi) >> 1;
int nval = Myquery(vector<int> (cur.begin() + L, cur.begin() + mid + 1));
if (nval + reduction(vector<int> (cur.begin() + L, cur.begin() + mid + 1)) > val) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (lo < cur.size()) {
on.insert(cur[lo]);
}
L = lo + 1;
}
}
for (int a : nodes[v]) {
nodes[u].push_back(a);
}
}
// debug("after subtree", u, on);
vector<int> cur;
for (int b : nodes[u]) {
if (ad[u][b] != -1) cur.push_back(ad[u][b]);
}
int L = 0;
while (L < cur.size()) {
int val = Myquery({});
int lo = L, hi = cur.size();
while (lo < hi) {
int mid = (lo + hi) >> 1;
int nval = Myquery(vector<int> (cur.begin() + L, cur.begin() + mid + 1));
if (nval + reduction(vector<int> (cur.begin() + L, cur.begin() + mid + 1)) > val) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (lo < cur.size()) {
on.insert(cur[lo]);
}
L = lo + 1;
}
nodes[u].push_back(u);
// debug("end", u, on);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
if (N == 2) {
return {0};
}
memset(ad, -1, sizeof ad);
memset(par, -1, sizeof par);
n = N, m = U.size();
for (int i = 0; i < m; i++) {
ad[U[i]][V[i]] = ad[V[i]][U[i]] = i;
edges.push_back({U[i], V[i]});
}
{
DSU dsu(n);
for (int i = 0; i < m; i++) {
auto [u, v] = edges[i];
if (dsu.unite(u, v)) {
// cout << u << " " << v << endl;
tree.insert(i);
g[u].push_back(v);
g[v].push_back(u);
}
}
}
init = query(vector<int> (tree.begin(), tree.end()));
// debug(init);
init_parent(0, -1);
for (int u = 0; u < n; u++) {
if (g[u].size() == 1) continue;;
for (int v : g[u]) {
if (v == par[u]) continue;
bool found = false, ok = true;
for (int vv : g[u]) {
if (v == vv) continue;
if (found) break;
auto one = get(v, u), other = get(vv, u);
for (int a : one) {
if (found) break;
for (int b : other) {
if (ad[a][b] != -1) {
int v1 = init;
auto ntree = tree;
ntree.erase(ad[u][vv]);
ntree.insert(ad[a][b]);
int v2 = query(vector<int> (ntree.begin(), ntree.end()));
ntree.insert(ad[u][vv]);
ntree.erase(ad[u][v]);
int v3 = query(vector<int> (ntree.begin(), ntree.end()));
if (v3 >= max(v1, v2)) ok = false;
found = true;
break;
}
}
}
}
if (ok) on.insert(ad[u][v]);
}
}
// debug(tree, on);
dfs(0, -1);
// debug(on);
return vector<int> (on.begin(), on.end());
}
