#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> G;
vector<vector<int>> csz;
vector<int> sz;
void dfs(int u, int p){
if(p != 0) {
G[u].erase(find(G[u].begin(), G[u].end(), p));
G[u].push_back(p);
}
csz[u].clear();
sz[u] = 1;
for(int c: G[u]){
if(c != p){
dfs(c, u);
sz[u] += sz[c];
csz[u].push_back(sz[c]);
}
}
if(p) csz[u].push_back(n - sz[u]);
}
void Parse(vector<pair<int,int>> F){
n = F.size() + 1;
G.clear();
G.resize(n + 1);
csz.resize(n + 1);
for(pair<int,int> e: F){
int u = e.first, v = e.second;
G[u].push_back(v);
G[v].push_back(u);
}
sz.clear();
sz.resize(n + 1, 0);
dfs(1, 0);
}
void dfs1(int u, int p, vector<int> &mk){
if(p){
int idx = find(G[u].begin(), G[u].end(), p) - G[u].begin();
int mx = *max_element(csz[u].begin(), csz[u].end());
mk[u] = (csz[u][idx] == mx);
}
for(int c: G[u]){
if(c != p){
dfs1(c, u, mk);
}
}
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
Parse(F);
vector<int> res(n + 1, 0);
dfs1(safe, 0, res);
res.erase(res.begin());
return res;
}
template<class T>
void Erase(vector<T> &v, T e){
auto it = find(v.begin(), v.end(), e);
if(it == v.end()) return;
v.erase(it);
}
void locate(vector<pair<int, int>> F, int curr, int t) {
Parse(F);
mt19937 rng(1234);
shuffle(F.begin(), F.end(), rng);
vector<int> vmx(n + 1);
vector<vector<int>> vu[2];
vu[0].resize(n + 1);
vu[1].resize(n + 1);
for(int i = 1; i <= n; i++){
vmx[i] = *max_element(csz[i].begin(), csz[i].end());
for(int j = 0; j < G[i].size(); j++){
vu[csz[i][j] == vmx[i]][i].push_back(G[i][j]);
}
}
int pre = curr;
while(1){
if(vu[t][curr].empty()) {
if(t){
visit(pre);
}
break;
}
int nxt = vu[t][curr].back();
// vu[t][curr].pop_back();
int ct = t;
t = visit(nxt);
if(vu[ct][curr].size() == 1){
Erase(vu[t][nxt], curr);
Erase(vu[t^1][nxt], curr);
}
pre = curr;
curr = nxt;
}
}
