#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define f first
#define s second
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {int f=0;os<<'{';for(auto&i:x)os<<(f++ ? ", " : ""),os<<i;os<<"}";return os;}
void _print() {cerr << "]\n";}
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
vector<int>mark(vector<pii>f,int l){
int n=f.size()+1;
vector<vector<int>>adj(n);for(auto i:f)adj[i.f-1ll].push_back(i.s-1ll),adj[i.s-1ll].push_back(i.f-1ll);
l--;
vector<int>sz(n,1),d(n,0);
function<void(int,int,vector<int>&)>dfs=[&](int u,int p,vector<int>&d){
for(int i:adj[u]){
if(i==p)continue;
d[i]=d[u]+1; dfs(i,u,d);sz[u]+=sz[i];
}
};
vector<int>centroids;
function<void(int,int)>dfs2=[&](int u,int p){
bool works=1;
for(int i:adj[u]){
if(sz[i]*2>n)works=0;
if(i==p)continue;
int og=sz[u],v=sz[i];
sz[u]-=sz[i];
sz[i]+=sz[u];
dfs2(i,u);
sz[u]=og;sz[i]=v;
}
if(works)centroids.push_back(u);
};
dfs(l,-1,d);
dfs2(l,-1);
dbg(centroids);
assert(centroids.size()<=2);
int cent=centroids[0];
if(centroids.size()>1 and d[cent]>d[centroids[1]]){
cent=centroids[1];
}
vector<int>d2(n,0);
dfs(cent,-1,d2);
vector<int>ret(n);for(int i=0;i<n;i++)ret[i]=(d[i]+d2[i]==d[cent]);
dbg(d,d2);
dbg(ret);
return ret;
}
void locate(vector<pii>f,int cur,int t){
// we can call visit
int n=f.size()+1;
vector<vector<int>>adj(n);for(auto i:f)adj[i.f-1ll].push_back(i.s-1ll),adj[i.s-1ll].push_back(i.f-1ll);
vector<int>sz(n,1),d(n,0);
function<void(int,int,vector<int>&)>dfs=[&](int u,int p,vector<int>&d){
for(int i:adj[u]){
if(i==p)continue;
d[i]=d[u]+1; dfs(i,u,d);sz[u]+=sz[i];
}
};
vector<int>centroids;
function<void(int,int)>dfs2=[&](int u,int p){
bool works=1;
for(int i:adj[u]){
if(sz[i]*2>n)works=0;
if(i==p)continue;
int og=sz[u],v=sz[i];
sz[u]-=sz[i];
sz[i]+=sz[u];
dfs2(i,u);
sz[u]=og;sz[i]=v;
}
if(works)centroids.push_back(u);
};
dfs(0,-1,d);
dfs2(0,-1);
dbg(centroids);
// we have found our centroids
// now we need to root it at the centroids (pretend they merge) and go towards them until t is satisfied
vector<int>p(n),s(n,1);
vector<int>checked(n),val(n);
function<void(int,int)>dfs3=[&](int u,int par){
p[u]=par;
for(int i:adj[u]){
if(i==par)continue;
dfs3(i,u);
s[u]+=s[i];
}
};
assert(1<=centroids.size() and centroids.size()<=2);
dfs3(centroids[0],-1);
cur--;
checked[cur]=1;val[cur]=t;
while(!t){
if(p[cur]==-1)break;
t=visit(p[cur]+1);
checked[p[cur]]=1;
val[p[cur]]=t;
cur=p[cur];
}
if(t==false){
t=visit(centroids[1]+1);cur=centroids[1];
}
dbg(cur);
// t is true rn so we need to descend now
while(true){
vector<int>kids;for(int i:adj[cur])if(i!=p[cur])kids.push_back(i);
sort(all(kids),[&](int i,int j){return s[i]>s[j];});
bool moved=0;
for(int i:kids){
if(checked[i] and val[i]){
visit(i+1);cur=i;t=1;moved=1;break;
}else if(checked[i])continue;
int v=visit(i+1);
if(v){cur=i;t=v;moved=1;break;}
visit(cur+1);
}
if(!moved){
dbg(cur);
break;
}
}
dbg("END");
}
