#include <bits/stdc++.h>
using namespace std;
#include "incursion.h"
int n;
vector<int> adj[45010];
vector<int> cen;
int siz[45010];
int par[45010];
void f(int x, int p)
{
bool ok = 1;
siz[x] = 1;
for(int y : adj[x])
{
if(y == p)
continue;
f(y, x);
siz[x] += siz[y];
if(siz[y] > n / 2)
ok = 0;
}
if(n - siz[x] > n / 2)
ok = 0;
if(ok)
cen.push_back(x);
}
void g(int x, int p)
{
par[x] = p;
siz[x] = 1;
for(int y : adj[x])
{
if(y == p)
continue;
g(y, x);
siz[x] += siz[y];
}
}
void init(vector<pair<int, int>> &F)
{
n = (int)F.size() + 1;
for(auto [x, y] : F)
{
adj[x].push_back(y);
adj[y].push_back(x);
}
f(1, -1);
if((int)cen.size() == 1)
cen.push_back(-1);
assert((int)cen.size() == 2);
g(cen[0], cen[1]);
if(cen[1] != -1)
g(cen[1], cen[0]);
}
vector<int> mark(vector<pair<int, int>> F, int safe)
{
init(F);
vector<int> res(n);
int x = safe;
while(x != -1)
{
res[x - 1] = 1;
x = par[x];
}
return res;
}
void locate(vector<pair<int, int>> F, int curr, int t)
{
init(F);
int x = curr;
while(t == 0)
{
t = visit(par[x]);
x = par[x];
}
while(1)
{
vector<pair<int, int>> nx;
for(int y : adj[x])
{
if(y == par[x])
continue;
nx.push_back({ siz[y], y });
}
sort(nx.rbegin(), nx.rend());
bool ok = 1;
for(auto [_, y] : nx)
{
if(visit(y))
{
ok = 0;
x = y;
break;
}
visit(x);
}
if(ok)
return;
}
}
