#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];
int cnt;
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 par[u] = (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) {
cnt++;
return count_common_roads(r);
}
set<int> tree;
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;
}
bool vis[mxN];
int in[mxN], out[mxN], par[mxN], timer;
void find_tree(int u) {
in[u] = ++timer;
vis[u] = true;
for (int v = 0; v < n; v++) {
if (ad[u][v] != -1 && !vis[v]) {
g[u].push_back(v);
tree.insert(ad[u][v]);
par[v] = u;
find_tree(v);
}
}
out[u] = timer;
}
bool done[mxN * mxN];
vector<int> Q, new_on;
void solve(int l, int r) {
if (l > r) return;
int val = Myquery(vector<int> (Q.begin() + l, Q.begin() + r + 1));
int red = reduction(vector<int> (Q.begin() + l, Q.begin() + r + 1));
auto x = vector<int> (Q.begin() + l, Q.begin() + r + 1);
// debug(on, x, val, red);
if (val + red <= init) return;
if (l == r) {
new_on.push_back(Q[l]);
return;
}
int m = (l + r) >> 1;
solve(l, m);
solve(m + 1, r);
}
vector<int> dfs(int u, int p) {
vector<int> V;
for (int v : g[u]) {
if (v == p) continue;
auto r = dfs(v, u);
for (int i : r) V.push_back(i);
}
vector<int> cur;
for (int i : V) {
if (ad[u][i] != -1 && !done[ad[u][i]]) cur.push_back(ad[u][i]);
}
init = Myquery({});
Q = cur;
// debug(u, Q);
solve(0, Q.size() - 1);
for (int i : new_on) on.insert(i);
new_on.clear();
// 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;
// }
V.push_back(u);
return V;
}
bool insubtree(int u, int v) {
return (in[u] <= in[v] && out[v] <= out[u]);
}
void get(int u, int v, int a, int b) {
vector<int> path = {ad[a][b]};
int aa = a;
while (aa != b) {
path.push_back(ad[aa][par[aa]]);
aa = par[aa];
}
int val = -1;
for (int i : path) {
if (done[i]) {
set<int> ntree = tree;
ntree.erase(i);
ntree.insert(ad[a][b]);
int v = query(vector<int> (ntree.begin(), ntree.end()));
if (v == init) val = on.count(i);
else val = on.count(i) ^ 1;
break;
}
}
vector<int> store(path.size(), -1);
if (val == -1) {
int mx = init;
set<int> ntree = tree;
ntree.insert(ad[a][b]);
int idx = 1;
for (int i : path) {
if (i == ad[a][b]) continue;
ntree.erase(i);
mx = max(mx, store[idx] = query(vector<int> (ntree.begin(), ntree.end())));
ntree.insert(i);
idx++;
}
if (mx > init) val = 1;
else val = 0;
}
if (val == 1) on.insert(ad[a][b]);
for (int i = 1; i < path.size(); i++) {
if (done[path[i]]) continue;
auto ntree = tree;
ntree.insert(ad[a][b]);
ntree.erase(path[i]);
int q = (store[i] == -1 ? query(vector<int> (ntree.begin(), ntree.end())) : store[i]);
// debug(edges[path[i]], a, b, q);
if (val == 1) {
if (q == init) on.insert(path[i]);
} else {
if (q < init) on.insert(path[i]);
}
}
for (int i : path) done[i] = true;
}
void find_tree_edges() {
find_tree(0);
// debug(tree);
// for (int i : tree) debug(edges[i]);
init = query(vector<int> (tree.begin(), tree.end()));
for (int u = 0; u < n; u++) {
for (int v : g[u]) {
if (done[ad[u][v]]) continue;
for (int i = 0; i < m; i++) {
auto [a, b] = edges[i];
if (i == ad[u][v]) continue;
if (insubtree(v, a) && !insubtree(v, b)) {
get(u, v, a, b);
break;
}
if (insubtree(v, b) && !insubtree(v, a)) {
get(u, v, b, a);
break;
}
}
if (!done[ad[u][v]]) {
done[ad[u][v]] = true;
on.insert(ad[u][v]);
}
}
}
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
memset(par, -1, sizeof par);
if (N == 2) {
return {0};
}
memset(ad, -1, sizeof ad);
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]});
}
find_tree_edges();
assert(cnt <= 2 * n + 5);
// debug(on);
dfs(0, -1);
// debug(on);
return vector<int> (on.begin(), on.end());
}
