#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
typedef vector<int> vi;
#define f first
#define s second
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
safe--;
int n=F.size()+1;
vector<vi> adj(n);
for(auto i: F){
i.f--;i.s--;
adj[i.f].push_back(i.s);
adj[i.s].push_back(i.f);
}
vi sz(n);
function<int(int,int)> get_size=[&](int v, int p)->int{
sz[v]=1;
for(auto u: adj[v]){
if(u==p)continue;
sz[v]+=get_size(u,v);
}
return sz[v];
};
get_size(0,-1);
function<int(int,int,int)> find_ce=[&](int v, int p,int s)->int{
for(auto u: adj[v]){
if(u==p)continue;
if(sz[u]>=s)
return find_ce(u,v,s);
}
return v;
};
int ce=find_ce(0,-1,n/2);
vi marked(n);
function<int(int, int)> mark_nodes=[&](int v, int p)->int{
if(v==safe){
marked[v]=1;
return 1;
}
for(auto u: adj[v]){
if(u==p)continue;
marked[v]|=mark_nodes(u,v);
}
return marked[v];
};
mark_nodes(ce,-1);
return marked;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
curr--;
int n=F.size()+1;
vector<vi> adj(n);
for(auto i: F){
i.f--;i.s--;
adj[i.f].push_back(i.s);
adj[i.s].push_back(i.f);
}
vi sz(n),pa(n);
function<int(int,int)> get_size=[&](int v, int p)->int{
sz[v]=1;
pa[v]=p;
for(auto u: adj[v]){
if(u==p)continue;
sz[v]+=get_size(u,v);
}
return sz[v];
};
get_size(0,-1);
function<int(int,int,int)> find_ce=[&](int v, int p,int s)->int{
for(auto u: adj[v]){
if(u==p)continue;
if(sz[u]>=s)
return find_ce(u,v,s);
}
return v;
};
int ce=find_ce(0,-1,n/2);
get_size(ce,-1);
// for(auto u: adj[ce]){
// if(sz[u]>=n/2&&pa[u]!=ce){
// pa[ce]=u;
// }
// }
vi used(n);
// cerr<<"--"<<ce<<endl;
// for(auto i: pa)cout<<i<<" ";
// cout<<endl;
// int x=100;
// while(x--){
while(true){
used[curr]=1;
if(t==0){
t=visit(pa[curr]+1);
curr=pa[curr];
}
else{
vi tmp;
for(auto u: adj[curr]){
if(u==pa[curr]||used[u])continue;
tmp.push_back(u);
}
if(tmp.empty()){
return;
}
sort(tmp.begin(),tmp.end(), [&](int a, int b){return sz[a]>sz[b];});
t=visit(tmp[0]+1);
curr=tmp[0];
}
}
}
