#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e2 + 20;
const int maxM = maxN * maxN / 2;
pair<int, int> edges[maxM];
vector<pair<int, int>> adj[maxM];
vector<int> adj_id[maxN];
int deg[maxN];
pair<int, int> high[maxN];
int par[maxN];
int par_id[maxN];
int depth[maxN];
int flag[maxM];
vector<int> cycle[maxM];
vector<int> tree;
int N, M;
void dfs(int u, int p) {
flag[u] = true;
high[u] = make_pair(depth[u], -1);
for (auto e: adj[u]) {
int v = e.first;
int id = e.second;
if (v == p) {
continue;
}
if (!flag[v]) {
depth[v] = depth[u] + 1;
par[v] = u;
par_id[v] = id;
dfs(v, u);
high[u] = min(high[u], high[v]);
}
else {
high[u] = min(high[u], make_pair(depth[v], id));
}
}
}
int query_cycle(int i, int j) {
tree.erase(find(tree.begin(), tree.end(), j));
tree.push_back(i);
int res = count_common_roads(tree);
tree.pop_back();
tree.push_back(j);
return res;
}
int root(int u) {
if (par[u] == -1) {
return u;
}
else {
return par[u] = root(par[u]);
}
}
bool join(int u, int v) {
int ru = root(u);
int rv = root(v);
if (ru == rv) {
return false;
}
if (depth[ru] > depth[rv]) {
swap(ru, rv);
}
par[ru] = rv;
if (depth[ru] == depth[rv]) {
depth[rv]++;
}
return true;
}
int query_tree(vector<int> query) {
for (int i = 0; i < N; i++) {
depth[i] = 0;
par[i] = -1;
}
for (auto id: query) {
join(edges[id].first, edges[id].second);
}
int extra = 0;
for (auto id: tree) {
if (join(edges[id].first, edges[id].second)) {
extra += flag[id];
query.push_back(id);
}
}
return count_common_roads(query) - extra;
}
vector<int> find_roads(int _N, vector<int> U, vector<int> V) {
N = _N;
M = U.size();
for (int i = 0; i < M; i++) {
edges[i] = make_pair(U[i], V[i]);
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
dfs(0, -1);
for (int i = 0; i < N; i++) {
adj[i].clear();
}
for (int i = 0; i < M; i++) {
flag[i] = -1;
}
for (int i = 1; i < N; i++) {
tree.push_back(par_id[i]);
if (high[i].second == -1) {
flag[par_id[i]] = 1;
}
else {
cycle[high[i].second].push_back(par_id[i]);
}
}
int orig = count_common_roads(tree);
for (int i = 0; i < M; i++) {
if (cycle[i].empty()) {
continue;
}
int u = U[i];
int v = V[i];
if (depth[u] < depth[v]) {
swap(u, v);
}
while (par[u] != v) {
u = par[u];
}
vector<pair<int, int>> cnt;
cnt.emplace_back(i, orig);
cnt.emplace_back(par_id[u], query_cycle(i, par_id[u]));
for (auto j: cycle[i]) {
cnt.emplace_back(j, query_cycle(i, j));
}
for (auto p1: cnt) {
for (auto p2: cnt) {
adj[p1.first].emplace_back(p2.first, p1.second - p2.second);
}
}
}
for (int i = 0; i < M; i++) {
if (flag[i] != -1) {
continue;
}
for (auto e: adj[i]) {
if (e.second == -1) {
flag[i] = 1;
}
if (e.second == 1) {
flag[i] = 0;
}
}
if (flag[i] != -1) {
deque<int> q;
q.push_back(i);
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto e: adj[u]) {
int v = e.first;
if (flag[v] == -1) {
flag[v] = flag[u] + e.second;
q.push_back(v);
}
}
}
}
}
for (auto id: tree) {
if (flag[id] == -1) {
flag[id] = 0;
}
}
for (int i = 0; i < M; i++) {
adj_id[U[i]].push_back(i);
adj_id[V[i]].push_back(i);
}
for (int i = 0; i < N; i++) {
deg[i] = query_tree(adj_id[i]);
}
vector<int> res;
for (int i = 0; i < N - 1; i++) {
for (int u = 0; u < N; u++) {
if (deg[u] != 1) {
continue;
}
vector<int> cand = adj_id[u];
while ((int)cand.size() > 1) {
int sz = cand.size();
vector<int> left(cand.begin(), cand.begin() + sz / 2);
vector<int> right(cand.begin() + sz / 2, cand.end());
if (query_tree(left)) {
cand = left;
}
else {
cand = right;
}
}
int id = cand[0];
int v = (U[id] == u ? V[id] : U[id]);
adj_id[u].erase(find(adj_id[u].begin(), adj_id[u].end(), id));
adj_id[v].erase(find(adj_id[v].begin(), adj_id[v].end(), id));
deg[u]--;
deg[v]--;
res.push_back(id);
}
}
return res;
}
