#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
int h[50005], p[50005], l[50005], r[50005];
vector<int> adj[50005];
void dfs(int x)
{
for (auto y: adj[x])
{
if (y!=p[x])
{
p[y]=x; l[x]=y;
h[y]=h[x]+1;
dfs(y);
};
};
}
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);
};
for (i=1; i<=n; i++)
{
if (adj[i].size()==1) {break;};
};
h[i]=1;
dfs(i);
vector<int> T(n);
for (i=0; i<n; i++) {T[i]=0;};
if (n%2==0)
{
if (h[safe]<=(n+1)/2)
{
while (h[safe]<=(n+1)/2) {T[safe-1]=1; safe=l[safe];};
}
else
{
while (h[safe]>(n+1)/2) {T[safe-1]=1; safe=p[safe];};
};
}
else
{
while (h[safe]!=(n+1)/2)
{
if (h[safe]<(n+1)/2) {T[safe-1]=1; safe=l[safe];}
else {T[safe-1]=1; safe=p[safe];};
};
T[safe-1]=1;
};
return T;
}
void locate(vector<pair<int, int>> F, int curr, int t)
{
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);
};
for (i=1; i<=n; i++)
{
if (adj[i].size()==1) {break;};
};
h[i]=1;
dfs(i);
if (t==0)
{
if (h[curr]<=(n+1)/2)
{
do {curr=l[curr]; i=visit(curr);}
while (i==0);
}
else
{
do {curr=p[curr]; i=visit(curr);}
while (i==0);
};
};
if (n%2==1 && h[curr]==(n+1)/2)
{
i=visit(p[curr]);
if (i==0)
{
i=visit(curr);
i=visit(l[curr]);
curr=l[curr];
}
else {curr=p[curr];};
};
if (h[curr]>(n+1)/2)
{
if (h[curr]==n) {return;};
do {curr=l[curr]; i=visit(curr);}
while (h[curr]<n && i==1);
if (i==1) {return;}
else {curr=p[curr]; i=visit(curr); return;};
}
else
{
if (h[curr]==1) {return;};
do {curr=p[curr]; i=visit(curr);}
while (h[curr]>1 && i==1);
if (i==1) {return;}
else {curr=l[curr]; i=visit(curr); return;};
};
}
