#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p;
DSU() = default;
DSU(int n) : p(n) {
iota(p.begin(), p.end(), 0);
}
int leader(int x) {
while (x != p[x]) x = p[x] = p[p[x]];
return x;
}
bool unite(int x, int y) {
x = leader(x), y = leader(y);
if (x == y) {
return false;
}
p[y] = x;
return true;
}
bool same(int x, int y) {
return leader(x) == leader(y);
}
};
vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V) {
const int m = U.size();
vector<int> type(m, -1);
vector idx(n, vector<int>(n, -1));
for (int i = 0; i < m; ++i) {
idx[U[i]][V[i]] = idx[V[i]][U[i]] = i;
}
DSU d1(n);
vector<int> st, par(n, -1), tin(n, -1);
vector<bool> in_st(m);
int T = 0;
auto dfs = [&](auto self, int v) -> void {
tin[v] = T++;
for (int to = 0; to < n; ++to) {
if (tin[to] == -1 && idx[v][to] != -1) {
par[to] = v;
in_st[idx[v][to]] = true;
st.push_back(idx[v][to]);
self(self, to);
}
}
};
dfs(dfs, 0);
auto path = [&](int x, int y) {
if (tin[x] > tin[y]) {
swap(x, y);
}
vector<int> ans;
while (y != x) {
ans.push_back(idx[y][par[y]]);
y = par[y];
}
return ans;
};
const int init = count_common_roads(st);
for (int i = 0; i < m; ++i) {
if (!in_st[i]) {
auto p = path(U[i], V[i]);
sort(p.begin(), p.end());
int done = -1, not_done = -1;
for (int x: p) {
if (type[x] != -1) {
done = x;
} else {
not_done = x;
}
}
if (done != -1) {
if (not_done == -1) {
continue;
}
set<int> sp(st.begin(), st.end());
sp.insert(i);
sp.erase(done);
int aim = count_common_roads(vector(sp.begin(), sp.end()));
sp.insert(done);
for (int x: p) {
if (type[x] == -1) {
sp.erase(x);
int now = count_common_roads(vector(sp.begin(), sp.end()));
sp.insert(x);
type[x] = type[done] ^ (now != aim);
}
}
} else {
set<int> sp(st.begin(), st.end());
sp.insert(i);
int mx = init, mn = init;
vector<pair<int, int>> save{{init, i}};
for (int x: p) {
sp.erase(x);
int now = count_common_roads(vector(sp.begin(), sp.end()));
sp.insert(x);
mx = max(mx, now), mn = min(mn, now);
save.emplace_back(now, x);
}
for (auto [now, x]: save) {
if (mn == mx) {
type[x] = 0;
} else {
type[x] = now != mx;
}
}
}
}
}
for (int i : st) {
if (type[i] == -1) {
type[i] = 1;
}
}
auto howMany = [&](vector<int> a) {
DSU d(n);
for (int i: a) {
assert(d.unite(U[i], V[i]));
}
int cnt = 0;
for (int p : st) {
if (d.unite(U[p], V[p])) {
a.push_back(p);
cnt += type[p];
}
}
assert(a.size() == n - 1);
return count_common_roads(a) - cnt;
};
for (int v = 0; v < n; ++v) {
vector<int> need;
for (int to = 0; to < n; ++to) {
if (idx[v][to] != -1 && type[idx[v][to]] == -1) {
need.push_back(idx[v][to]);
}
}
auto solve = [&](auto self, vector<int> a, int cnt) -> void {
if (cnt == 0) {
for (int i : a) {
type[i] = 0;
}
return;
}
if (a.size() == 1) {
type[a[0]] = 1;
return;
}
vector<int> L(a.begin(), a.begin() + a.size() / 2);
vector<int> R(a.begin() + a.size() / 2, a.end());
int have = howMany(L);
self(self, L, have);
self(self, R, cnt - have);
};
solve(solve, need, howMany(need));
}
st.clear();
for (int i = 0; i < m; ++i) {
assert(type[i] != -1);
if (type[i] == 1) {
st.push_back(i);
}
}
assert(st.size() == n - 1);
return st;
}
