#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const int N=46000;
vector<int> ma[N];
int dist[N];
void dfs(int x,int p=-1,int h=0)
{
dist[x]=h;
for(auto y:ma[x])
{
if(y!=p)
{
dfs(y,x,h+1);
}
}
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
int n=F.size()+1;
for(int i=0;i<=n;i++)
{
ma[i].clear();
}
for(int i=0;i<n-1;i++)
{
ma[F[i].first].push_back(F[i].second);
ma[F[i].second].push_back(F[i].first);
}
dfs(safe);
vector<int> dp(n);
for(int i=1;i<=n;i++)dp[i-1]=dist[i];
return dp;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
int n=F.size()+1;
for(int i=0;i<=n;i++)
{
ma[i].clear();
}
for(int i=0;i<n-1;i++)
{
ma[F[i].first].push_back(F[i].second);
ma[F[i].second].push_back(F[i].first);
}
int par=-1;
while(t!=0)
{
int pt=t,pc=curr;;
if(ma[curr].size()==1)
{
curr=ma[curr][0];
t=visit(curr);
par=pc;
continue;
}
if(ma[curr].size()==2)
{
if(ma[curr][0]==par)
{
curr=ma[curr][1]; // directly go to the other one
t=visit(curr);
}
else if(ma[curr][1]==par){
curr=ma[curr][0]; // directly go to the other one
t=visit(curr);
}
else{
curr=ma[curr][1]; // directly go to the other one
t=visit(curr);
if(t>pt) // moving away from safe
{
visit(pc);
t=visit(ma[pc][0]);
curr=ma[pc][0];
}
}
par=pc;
continue;
}
}
return;
}
