#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 45000 + 5;
int n;
vector<int> g[NM], ans;
int dfs(int u, int p = -1)
{
int sz = 1, mx = 0;
for (int v : g[u])
if (u != p)
{
auto t = dfs(v, u);
setmax(mx, t);
}
ans[u] = n - sz > mx;
return sz;
}
vector<int> mark(vector<pair<int, int>> F, int safe)
{
n = F.size() + 1;
for (auto t : F)
g[t.fi].push_back(t.se), g[t.se].push_back(t.fi);
ans.resize(n);
dfs(safe);
return ans;
}
int sz[NM], dep[NM];
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 vis[NM];
void locate(vector<pair<int, int>> F, int curr, int t)
{
n = F.size() + 1;
for (auto t : F)
g[t.fi].push_back(t.se), g[t.se].push_back(t.fi);
dfs_sz(0);
for (int i = 0; i < n; i++)
sort(all(g[i]), [&](int x, int y){return SZ(i, x) < SZ(i, y);});
while (1)
{
vis[curr] = 1;
if (g[curr].empty())
break;
if (t == 1)
t = visit(curr = g[curr].back());
else
{
bool siu = 0;
for (int x : g[curr])
if (x > g[curr][0] && !vis[x])
t = visit(curr = x), siu = 1;
if (!siu)
break;
}
}
}
