#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// SUBTASK 1
vector<int> mark(vector<pair<int,int>> F,int safe){
int N = F.size()+1;
vector<int> direction(N);
vector<int> pos;
vector<vector<int>> adj(N+1);
for(int i=0;i<N-1;i++){
adj[F[i].first].emplace_back(F[i].second);
adj[F[i].second].emplace_back(F[i].first);
}
function<void(int,int)> dfs = [&](int x,int p){
pos.emplace_back(x);
for(int&i:adj[x])if(i!=p)dfs(i,x);
};
for(int i=1;i<=N;i++)if(adj[i].size()==1){dfs(i,-1);break;}
int goMe = -1;
for(int i=0;i<N;i++)if(pos[i]==safe)goMe=i;
if(N&1 and goMe==N/2){
// EDGE CASE
for(int i=0;i<goMe;i++)direction[pos[i]-1]=1;
for(int i=goMe+1;i<N;i++)direction[pos[i]-1]=1;
} else {
if(N&1){
if(goMe<N/2){
for(int i=N/2;i<N;i++)direction[pos[i]-1]=1;
for(int i=goMe;i<N/2;i++)direction[pos[i]-1]=0;
for(int i=0;i<goMe;i++)direction[pos[i]-1]=1;
} else {
for(int i=0;i<=N/2;i++)direction[pos[i]-1]=1;
for(int i=N/2+1;i<=goMe;i++)direction[pos[i]-1]=0;
for(int i=goMe+1;i<N;i++)direction[pos[i]-1]=1;
}
} else {
if(goMe<N/2){
for(int i=N/2;i<N;i++)direction[pos[i]-1]=1;
for(int i=goMe;i<N/2;i++)direction[pos[i]-1]=0;
for(int i=0;i<goMe;i++)direction[pos[i]-1]=1;
} else {
for(int i=0;i<N/2;i++)direction[pos[i]-1]=1;
for(int i=N/2;i<=goMe;i++)direction[pos[i]-1]=0;
for(int i=goMe+1;i<N;i++)direction[pos[i]-1]=1;
}
}
}
return direction;
}
void locate(vector<pair<int,int>> F,int curr,int t){
int N = F.size()+1;
vector<int> pos;
vector<vector<int>> adj(N+1);
for(int i=0;i<N-1;i++){
adj[F[i].first].emplace_back(F[i].second);
adj[F[i].second].emplace_back(F[i].first);
}
function<void(int,int)> dfs = [&](int x,int p){
pos.emplace_back(x);
for(int&i:adj[x])if(i!=p)dfs(i,x);
};
for(int i=1;i<=N;i++)if(adj[i].size()==1){dfs(i,-1);break;}
int currPos = -1;
for(int i=0;i<N;i++)if(pos[i]==curr)currPos=i;
vector<bool> visited(N);
if(N&1){
while(true){
visited[currPos]=true;
if(currPos==N/2){
if(t==0)return;
else {
if(!visited[currPos+1]){
t = visit(pos[++currPos]);
continue;
}
if(!visited[currPos-1]){
t = visit(pos[--currPos]);
continue;
}
}
} else if(currPos<N/2){
if(t==1){
t = visit(pos[++currPos]);
if(currPos!=N/2 and visited[currPos])return;
} else if(t==0){
if(currPos==0)return;
t=visit(pos[--currPos]);
if(visited[currPos]){
t = visit(pos[++currPos]);
return;
}
}
} else if(currPos>N/2){
if(t==1){
t = visit(pos[--currPos]);
if(currPos!=N/2 and visited[currPos]){
t = visit(pos[++currPos]);
return;
}
} else if(t==0){
if(currPos==N-1)return;
t=visit(pos[++currPos]);
if(visited[currPos])return;
}
}
}
} else {
while(true){
visited[currPos]=true;
if(currPos<N/2){
if(t==1){
t = visit(pos[++currPos]);
if(visited[currPos])return;
} else if(t==0){
if(currPos==0)return;
t=visit(pos[--currPos]);
if(visited[currPos]){
t = visit(pos[++currPos]);
return;
}
}
} else if(currPos>=N/2){
if(t==1){
t = visit(pos[--currPos]);
if(visited[currPos]){
t = visit(pos[++currPos]);
return;
}
} else if(t==0){
if(currPos==N-1)return;
t=visit(pos[++currPos]);
if(visited[currPos])return;
}
}
}
}
}
