#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
int root, h[50005], p[50005], l[50005], r[50005], sz[50005];
vector<int> adj[50005];
void dfs(int x)
{
sz[x]=1;
for (auto y: adj[x])
{
if (y!=p[x] && l[x]==0)
{
p[y]=x; l[x]=y;
h[y]=h[x]+1;
dfs(y);
sz[x]+=sz[y];
}
else if (y!=p[x])
{
p[y]=x; r[x]=y;
h[y]=h[x]+1;
dfs(y);
sz[x]+=sz[y];
};
};
}
int centroid(int x, int n)
{
for (auto y: adj[x])
{
if (y!=p[x] && sz[y]*2>n) {return centroid(y, n);};
};
return x;
}
vector<int> mark(vector<pair<int, int>> F, int safe)
{
int n=1, i;
for (auto p: F)
{
n=max(n, p.first);
n=max(n, p.second);
adj[p.first].push_back(p.second);
adj[p.second].push_back(p.first);
};
h[safe]=1;
dfs(safe);
vector<int> T(n);
for (i=0; i<n; i++) {T[i]=0;};
i=centroid(safe, n);
while (h[i]>=h[safe]) {T[i-1]=1; i=p[i];};
return T;
}
void locate(vector<pair<int, int>> F, int curr, int t)
{
int n=1, i, cent;
for (auto p: F)
{
n=max(n, p.first);
n=max(n, p.second);
adj[p.first].push_back(p.second);
adj[p.second].push_back(p.first);
};
h[curr]=1;
dfs(curr);
cent=centroid(curr, n);
for (i=1; i<=n; i++) {p[i]=l[i]=r[i]=h[i]=0;};
h[cent]=1;
dfs(cent);
if (t==0 && curr!=cent)
{
do {curr=p[curr]; i=visit(curr);}
while (curr!=cent && i==0);
};
if (l[curr]==0) {return;};
do
{
if (r[curr]>0 && sz[l[curr]]<=sz[r[curr]]) {curr=r[curr];}
else if (l[curr]>0) {curr=l[curr];}
else {return;};
i=visit(curr);
if (i==0)
{
curr=p[curr];
i=visit(curr);
if (r[curr]>0 && sz[l[curr]]<=sz[r[curr]]) {curr=l[curr];}
else if (r[curr]>0) {curr=r[curr];}
else {return;};
i=visit(curr);
};
}
while (i==1);
if (i==0) {curr=p[curr]; i=visit(curr);};
return;
}
