#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
#define ll long long
#define MOD 998244353
int n;
vector<int> sz, par, vis, res;
vector<vector<int>> g;
void dfs(int u, int v)
{
par[u] = v;
for (auto i : g[u]){
if (i != v){
dfs(i, u);
sz[u] += sz[i];
}
}
if(n - sz[u] >= (n + 1) / 2){
res[u - 1] = 1;
}
}
void dfs2(int u, int t)
{
vis[u] = 1;
if (t)
{
for (auto i : g[u]){
if ((sz[i] >= (n + 1) / 2 and !vis[i]) or (i == par[u] and n - sz[u] >= (n + 1) / 2)){
dfs2(i, visit(i));
}
}
}
else
{
vector<pair<int, int>> tmp;
for (auto i : g[u]){
if (!vis[i] and i != par[u] and sz[i] < (n + 1) / 2){
tmp.push_back({sz[i], i});
}
}
sort(tmp.rbegin(), tmp.rend());
if (!tmp.empty()){
dfs2(tmp[0].second, visit(tmp[0].second));
}
}
}
vector<int> mark(vector<pair<int, int>> edg, int safe)
{
n = edg.size() + 1;
g.resize(n + 1);
par.resize(n + 1);
sz.resize(n + 1, 1);
res.resize(n);
for (auto i : edg){
g[i.first].push_back(i.second);
g[i.second].push_back(i.first);
}
dfs(safe, 0);
return res;
}
void locate(vector<pair<int, int>> edg, int curr, int t)
{
g.clear();
sz.clear();
par.clear();
vis.clear();
res.clear();
n = edg.size() + 1;
g.resize(n + 1);
vis.resize(n + 1);
par.resize(n + 1);
sz.resize(n + 1, 1);
res.resize(n);
for (auto i : edg){
g[i.first].push_back(i.second);
g[i.second].push_back(i.first);
}
dfs(curr, 0);
dfs2(curr, t);
}
