#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];
vector<int> path;
void dfs(int x,int p=-1,int h=0)
{
path.push_back(x);
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);
}
// path
path.clear();
for(int i=1;i<=n;i++)
{
if(ma[i].size()==1)
{
dfs(i);
break;
}
}
vector<int> dp(n);
bool seens=0;
int b=0;
for(auto x:path)
{
b++;
if(x==safe)
{
seens=1;
dp[x-1]=0; // uniquely determined s
continue;
}
if(seens)
{
if((b-1)<(n-b))
{
dp[x-1]=1;// go to closest leaf
}
else
{
dp[x-1]=2;// not to go coloest leaf
}
}
else
{
if((b-1)>(n-b))
{
dp[x-1]=1;// go to closest leaf
}
else
{
dp[x-1]=2;// not to go coloest leaf
}
}
// (b-1) (1) (n-b)
}
// dfs(safe);
// 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);
}
path.clear();
for(int i=1;i<=n;i++)
{
if(ma[i].size()==1)
{
dfs(i);
break;
}
}
for(int i=0;i<n;i++)
{
if(path[i]==curr)
{
// while(t!=0)
// {
// if(t==1)
// {
// if(i<(n-i-1))
// {
// visit()
// }
// }
// }
if(t==0)
{
return;
}
if(t==1) // go to closest
{
// i 1 n-i-1
if(i<(n-i-1))
{
while(i>0)
{
t=visit(path[i-1]);
if(t==0)
{
return;
}
i--;
}
}
else{
while(i<n-1)
{
t=visit(path[i+1]);
if(t==0)return;
i++;
}
return;
}
return;
}
if(t==2) // not gio clostest
{
if(i==(n-1-i))
{
// not sure case
int pt=t;
t=visit(path[i-1]);
if(t==1)
{
// we need to go toward i-1
i--;
}
else
{
// we need to go toward i+1
visit(path[i]);
t=visit(path[i+1]);
i++;
}
}
if(t==0)
{
return;
}
if(t==1) // go to closest
{
// i 1 n-i-1
if(i<(n-i-1))
{
while(i>0)
{
t=visit(path[i-1]);
if(t==0)
{
return;
}
i--;
}
}
else{
while(i<n-1)
{
t=visit(path[i+1]);
if(t==0)return;
i++;
}
return;
}
return;
}
else
{
// i 1 n-i-1
if(i>(n-i-1))
{
while(i>0)
{
t=visit(path[i-1]);
if(t==0)
{
return;
}
i--;
}
}
else{
while(i<n-1)
{
t=visit(path[i+1]);
if(t==0)return;
i++;
}
return;
}
return;
}
}
return;
}
}
// int par=-1;
// while(t!=0)
// {
// int pt=t,pc=curr;;
// int sz=ma[curr].size();
// for(int i=0;i<sz;i++)
// {
// if(ma[curr][i]==par)
// swap(ma[curr][i],ma[curr][sz-1]);
// }
// sz-=(ma[curr].back()==par); // we can ignore par
// if(sz==1)
// {
// curr=ma[curr][0];
// t=visit(curr);
// par=pc;
// continue;
// }
// if(sz==2)
// {
// 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;
// }
// if(sz==3)
// {
// continue;
// }
// }
return;
}
