#include "incursion.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 450005
using namespace std;
int n, root, sz[maxn], par[maxn], depth[maxn];
vector<int> adj[maxn];
void pfs(int u, int dad) {
par[u] = dad;
sz[u] = 1;
for (int v : adj[u])
if (v != dad) {
depth[v] = depth[u]+1;
pfs(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int dad) {
for (int v : adj[u])
if (v != dad && sz[v] > n/2) return find_centroid(v, u);
return u;
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
n = F.size()+1;
for (auto [u, v] : F) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
pfs(1, 0);
int centroid1 = find_centroid(1, 0), centroid2 = -1;
if (n % 2 == 0) {
for (int v : adj[centroid1])
if (v != par[centroid1] && sz[v] == n/2) {
centroid2 = v;
break;
}
if (sz[centroid1] == n/2) centroid2 = par[centroid1];
}
pfs(safe, 0);
if (centroid2 != -1 && depth[centroid1] > depth[centroid2]) swap(centroid1, centroid2);
vector<int> ans(n, 0);
while (centroid1) {
ans[centroid1-1] = 1;
centroid1 = par[centroid1];
}
return ans;
}
map<int, int> cached;
void locate(vector<pair<int, int>> F, int curr, int t) {
n = F.size()+1; cached.clear();
for (int i = 1; i <= n; i++) adj[i].clear();
for (auto [u, v] : F) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
pfs(1, 0);
root = find_centroid(1, 0);
pfs(root, 0);
cached[curr] = t;
while (t == 0 && curr != root) {
t = visit(curr = par[curr]);
cached[curr] = t;
}
cached[par[curr]] = -1;
while (1) {
int mxsz = -1, bigChild = -1;
for (int v : adj[curr])
if (!cached.count(v)) {
if (mxsz < sz[v]) {
mxsz = sz[v];
bigChild = v;
}
}
if (mxsz == -1) return;
int T = visit(bigChild);
cached[bigChild] = T;
if (T) {
curr = bigChild;
continue;
}
visit(curr);
}
}
