#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<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,int)> dfs = [&](int x,int p,int dep){
direction[x-1]=dep%3;
for(int&i:adj[x])if(i!=p)dfs(i,x,dep+1);
};
dfs(safe,-1,0);
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);
}
{
vector<int> dep(N+1);
function<int(int,int)> dfs = [&](int x,int p){
dep[x]=1;
for(int&i:adj[x])if(i!=p)dep[x]=max(dep[x],dfs(i,x)+1);
return dep[x];
};
dfs(curr,-1);
for(int i=1;i<=N;i++)
sort(adj[i].begin(),adj[i].end(),[&](const int &a,const int &b){return dep[a]>dep[b];});
}
function<bool(int,int)> dfs = [&](int x,int p){
int newt = visit(x);
if((newt+1)%3!=t){
visit(p);
return false;
}
t = newt;
for(int&i:adj[x])if(i!=p)if(dfs(i,x))return true;
return true;
};
for(int&i:adj[curr])if(dfs(i,curr))break;
}
