/* Author : Mychecksdead */
#include "incursion.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define cerr if(false) cerr
const int N = 50000;
vi g[N], put;
int s[N], n;
void dfs(int v, int p){
s[v] = 1;
int mx = -1;
for(int u: g[v]){
if(u != p){
dfs(u, v);
s[v] += s[u];
mx = max(mx, s[u]);
}
}
int parsz = n - s[v];
cerr << parsz << ' ' << mx <<'\n';
if(parsz >= mx){
put[v] = 0;
}else{
put[v] = 1;
}
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
n = F.size() + 1;
--safe;
for(int i = 0; i + 1 < n; ++i){
g[F[i].ff - 1].pb(F[i].ss - 1);
g[F[i].ss - 1].pb(F[i].ff - 1);
}
put.resize(n);
dfs(safe, safe);
return put;
}
vi G[N], go[N][2];
int S[N], m;
void dfs2(int v, int p){
S[v] = 1;
vector<pii> U;
for(int u: G[v]){
if(u != p){
dfs2(u, v);
S[v] += S[u];
U.pb({S[u], u});
}
}
if(v != p) U.pb({m - S[v], p});
sort(all(U), greater<pii>());
go[v][0].pb(U[0].ss);
for(int i = 1; i < U.size(); ++i){
if(U[i].ff == U[0].ff) go[v][0].pb(U[i].ss);
else go[v][1].pb(U[i].ss);
}
// cerr << v << '\n';
// for(int x: go[v][0]) cerr << x << ' '; cerr << '\n';
// for(int x: go[v][1]) cerr << x << ' '; cerr << '\n';
// cerr << '\n';
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
m = F.size() + 1;
vector<array<int, 2>> cnt(m + 2);
for(int i = 0; i + 1 < m; ++i){
G[F[i].ff].pb(F[i].ss);
G[F[i].ss].pb(F[i].ff);
}
int root = 1;
for(int i = 1; i <= m; ++i){
if(G[i].size() == 1) root = i;
}
dfs2(root, root);
int v = curr;
while(true){
cnt[v][t]++;
if(cnt[v][1] >= 3 && t == 1){
return;
}
if(t == 1 && go[v][1].size() == 0) return;
int nxt;
if(t == 0){
nxt = go[v][0][(cnt[v][0] - 1) % (int) go[v][0].size()];
}else{
nxt = go[v][1][(cnt[v][1] - 1) % (int) go[v][1].size()];
}
t = visit(nxt);
v = nxt;
}
return;
}
