#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "C:\debug.h"
#else
#define debug(...) 42
#endif
// If we can root the tree and HLD it then the problem is solved
// Using the property that a tree only have at most 2 centroid
// what a delight finding out this :D
vector<int> mark(vector<pair<int, int>> F, int safe) {
--safe;
int N = 0;
vector<vector<int>> g;
for (auto [u, v] : F) {
N = max({N, u--, v--});
g.resize(N);
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> sz(N), Max(N);
auto dfs = [&](auto self, int u, int p) -> void {
sz[u] = 1;
for (int v : g[u]) {
if (v ^ p) {
self(self, v, u);
sz[u] += sz[v];
Max[u] = max(Max[u], sz[v]);
}
}
};
dfs(dfs, 0, 0);
vector<int> cens;
for (int i = 0; i < N; ++i) {
if (max(Max[i], N - sz[i]) > N / 2) {
continue;
}
cens.push_back(i);
}
int root = cens[0];
vector<int> col(N, 0);
auto DFS = [&](auto self, int u, int p) -> bool {
if (u == safe) {
col[u] = 1;
return 1;
}
for (int v : g[u]) {
if (v ^ p && self(self, v, u)) {
col[u] = find(cens.begin(), cens.end(), v) == cens.end();
return 1;
}
}
return 0;
};
assert(DFS(DFS, root, root));
return col;
}
void locate(vector<pair<int, int>> F, int curr, int color) {
--curr;
int N = 0;
vector<vector<int>> g;
for (auto [u, v] : F) {
N = max({N, u--, v--});
g.resize(N);
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> sz(N), Max(N);
auto dfs = [&](auto self, int u, int p) -> void {
sz[u] = 1;
for (int v : g[u]) {
if (v ^ p) {
self(self, v, u);
sz[u] += sz[v];
Max[u] = max(Max[u], sz[v]);
}
}
};
dfs(dfs, 0, 0);
vector<int> cens;
for (int i = 0; i < N; ++i) {
if (max(Max[i], N - sz[i]) > N / 2) {
continue;
}
cens.push_back(i);
}
assert(cens.size() <= 2);
vector<int> pr(N);
fill(sz.begin(), sz.end(), 0);
auto DFS = [&](auto self, int u) -> void {
sz[u] = 1;
for (int v : g[u]) {
g[v].erase(find(g[v].begin(), g[v].end(), u));
pr[v] = u;
self(self, v);
sz[u] += sz[v];
}
};
int root = cens[0];
assert(cens.size() == 1 || find(g[root].begin(), g[root].end(), cens[1]) != g[root].end());
DFS(DFS, root);
// go up to root
int lst = -1;
while (color == 0 && curr ^ root) {
color = visit(pr[curr] + 1);
lst = curr;
curr = pr[curr];
}
if (color == 0) {
assert(cens.size() == 2);
color = visit(cens[1] + 1);
assert(color == 1);
lst = curr;
curr = cens[1];
}
if (curr == root && lst != -1) {
g[curr].erase(find(g[curr].begin(), g[curr].end(), lst));
}
// go down to the answer (do sth similar to HLD)
auto solve = [&](int u) {
if (g[u].empty()) {
return false;
}
int x = *max_element(g[u].begin(), g[u].end(), [&](int a, int b) {
return sz[a] < sz[b];
});
if (visit(x + 1)) {
curr = x;
return true;
}
visit(u + 1);
for (int v : g[u]) {
if (v ^ x) {
if (visit(v + 1)) {
curr = v;
return true;
}
visit(u + 1);
}
}
return false;
};
while (solve(curr));
}
