#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],par[1100000],c[1100000],h[1100000],siz[1100000],realcurr,realt,safe;
vector<ll> v[1100000],u;
pair<ll,pair<ll,ll>> p;
void Clear()
{
ll i;
u.clear();
for(i=1;i<=n;i++)
{
v[i].clear();
siz[i]=0;
par[i]=0;
h[i]=0;
c[i]=0;
}
}
void get_siz(ll x,ll y)
{
ll i;
siz[x]=1;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
get_siz(v[x][i],x);
siz[x]+=siz[v[x][i]];
}
}
ll centroid(ll x,ll y,ll z)
{
ll i;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
if(siz[v[x][i]]*2>n)
return centroid(v[x][i],x,z);
}
return x;
}
ll dfs(ll x,ll y)
{
if(x==t)
{
u[x-1]=1;
return 1;
}
if(x==0)
return 0;
ll i;
c[x]=1;
for(i=0;i<h[x];i++)
{
if(c[v[x][i]])
continue;
if(dfs(v[x][i],x))
{
u[x-1]=1;
return 1;
}
}
return 0;
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
n=F.size()+1;
Clear();
t=safe;
for(i=0;i<n-1;i++)
{
x=F[i].first;
y=F[i].second;
v[x].push_back(y);
v[y].push_back(x);
h[x]++;
h[y]++;
}
get_siz(1,0);
x=centroid(1,0,siz[1]);
get_siz(x,0);
y=0;
for(i=0;i<v[x].size();i++)
{
y=v[x][i];
if((n-siz[y])*2<=n)
{
break;
}
y=0;
}
c[x]=1;
c[y]=1;
u.resize(n);
dfs(x,0);
dfs(y,0);
return u;
}
ll ask(ll x)
{
if(x==0)
return 0;
if(realcurr==x)
{
return realt;
}
realcurr=x;
realt=visit(x);
return realt;
}
void f(ll x,ll y)
{
par[x]=y;
ll i;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y||c[v[x][i]])
continue;
f(v[x][i],x);
}
}
pair<ll,pair<ll,ll>> get_child(ll x)
{
ll i;
pair<ll,pair<ll,ll>> p={0,{0,0}};
for(i=0;i<h[x];i++)
{
if(v[x][i]==par[x]||c[v[x][i]])
continue;
if(p.first==0)
p.first=v[x][i];
else if(p.second.first==0)
p.second.first=v[x][i];
else
p.second.second=v[x][i];
}
return p;
}
ll subtree(ll x,ll y,ll z)
{
if(x==z)
return 1;
ll i;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y||c[v[x][i]])
continue;
if(subtree(v[x][i],x,z))
return 1;
}
return 0;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
n=F.size()+1;
Clear();
realcurr=curr;
realt=t;
for(i=0;i<n-1;i++)
{
x=F[i].first;
y=F[i].second;
v[x].push_back(y);
v[y].push_back(x);
h[x]++;
h[y]++;
}
get_siz(1,0);
x=centroid(1,0,siz[1]);
get_siz(x,0);
y=0;
for(i=0;i<v[x].size();i++)
{
y=v[x][i];
if((n-siz[y])*2<=n)
{
break;
}
y=0;
}
c[x]=1;
c[y]=1;
f(x,0);
f(y,0);
if(subtree(y,0,curr))
{
swap(x,y);
}
while(!t)
{
if(curr==x)
{
break;
}
curr=par[curr];
t=visit(curr);
}
if(t==0)
{curr=y;
swap(x,y);
t=visit(x);
}
get_siz(x,0);
while(1)
{
p=get_child(curr);
if(siz[p.first]<siz[p.second.first])
swap(p.first,p.second.first);
if(siz[p.first]<siz[p.second.second])
swap(p.first,p.second.second);
if(siz[p.second.first]<siz[p.second.second])
swap(p.second.first,p.second.second);
t=ask(p.first);
if(t==1)
{
curr=p.first;
continue;
}
t=ask(curr);
t=ask(p.second.first);
if(t==1)
{
curr=p.second.first;
continue;
}
t=ask(curr);
t=ask(p.second.second);
if(t==1)
{
curr=p.second.second;
continue;
}
t=ask(curr);
break;
}
return;
}
