#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];
vector<int> adj[maxn];
void pfs(int u, int dad) {
par[u] = dad;
sz[u] = 1;
for (int v : adj[u])
if (v != dad) {
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);
if (n % 2 == 0) {
int centroid2 = 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];
if (centroid2) {
if (safe == centroid1 || safe == centroid2) {
vector<int> ans(n, 0);
ans[safe-1] = 1;
return ans;
}
}
}
root = find_centroid(1, 0);
pfs(root, 0);
vector<int> ans(n, 0);
while (safe) {
ans[safe-1] = 1;
safe = par[safe];
}
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;
}
if (root == curr) {
for (int v : adj[curr]) {
if (cached.count(v)) continue;
int orz = visit(v);
cached[v] = orz;
if (!orz) {
visit(root);
continue;
}
curr = v;
t = orz;
}
if (curr == root) return;
}
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);
int last = curr;
for (int v : adj[curr])
if (!cached.count(v)) {
int orz = visit(v);
if (!orz) {
visit(curr);
return;
}
curr = orz;
cached[curr] = orz;
}
if (curr == last) return;
}
}
