#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#define setmax(x, y) x = max((x), (y))
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int NM = 45000 + 5;
int n, sz[NM], dep[NM], sf, par[NM];
vector<int> g[NM], ans;
int dfs_sz(int u, int p = -1)
{
sz[u] = 1;
for (int v : g[u])
if (v != p)
{
dep[v] = dep[u] + 1;
sz[u] += dfs_sz(v, u);
}
return sz[u];
}
int SZ(int u, int v)
{
return dep[u] < dep[v] ? sz[v] : n - sz[u];
}
bool cen(int u)
{
for (int v : g[u])
if (SZ(u, v) > n / 2)
return 0;
return 1;
}
int dfsm(int u, int p = 0)
{
for (int v : g[u])
if (v != p)
ans[u - 1] |= dfsm(v, u);
ans[u - 1] |= u == sf;
return ans[u - 1];
}
int dfsc(int u, int p = 0)
{
sz[u] = 1;
for (int v : g[u])
if (v != p)
{
dep[v] = dep[u] + 1;
par[v] = u;
sz[u] += dfsc(v, u);
}
return sz[u];
}
vector<int> mark(vector<pair<int, int>> F, int safe)
{
n = F.size() + 1, sf = safe;
for (auto t : F)
g[t.fi].push_back(t.se), g[t.se].push_back(t.fi);
dfs_sz(safe);
ans.resize(n);
int c = 0;
for (int i = 1; i <= n; i++)
if (cen(i))
{
if (c)
c = dep[i] < dep[c] ? i : c;
else
c = i;
}
dfsm(c);
return ans;
}
void locate(vector<pair<int, int>> F, int curr, int t)
{
n = F.size() + 1;
for (int i = 1; i <= n; i++)
g[i].clear();
for (auto t : F)
g[t.fi].push_back(t.se), g[t.se].push_back(t.fi);
dfs_sz(1);
int c;
for (int i = n; i >= 1; i--)
if (cen(i))
{
sort(all(g[i]), [&](int x, int y){return SZ(i, x) < SZ(i, y);});
c = i;
}
dfsc(c);
for (int i = 1; i <= n; i++)
if (par[i])
g[i].erase(find(all(g[i]), par[i]));
int u = curr;
while (!t && par[u])
{
g[par[u]].erase(find(all(g[par[u]]), u));
t = visit(u = par[u]);
}
int x = u;
while (!t || g[u].size())
{
if (u == x || t)
t = visit(u = g[u].back());
else
{
g[par[u]].erase(find(all(g[par[u]]), u));
t = visit(u = par[u]);
}
}
}
