#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define vl vector <long long>
#define ll long long
#define vll vector<vector<long long>>
vll graf;
vector<int> ans;
set<ll> vis;
vl counts;
void dfs(ll x, ll d){
ans[x-1] = d%3;
vis.insert(x);
for (ll i = 0; i < graf[x].size(); i++){
ll v = graf[x][i];
auto exist = vis.find(v);
if (exist == vis.end()){
dfs(v, d+1);
}
}
return;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
vis.clear();
graf.clear();
ans.clear();
long long N = F.size()+1;
ans.resize(N,0);
for (ll i = 0; i < N+1; i++){graf.push_back({});}
for (ll i = 0; i < F.size(); i++){
pair p = F[i];
graf[p.first].push_back(p.second);
graf[p.second].push_back(p.first);
}
dfs(safe, 0);
return ans;
}
void step(ll x, ll dist){
if (dist == 0){
dist = 3;
}
vl vektor = graf[x];
vector<pair<ll,ll>> opt;
for (ll i = 0; i < vektor.size(); i++){
opt.push_back({counts[vektor[i]], vektor[i]});
}
sort(opt.begin(), opt.end());
reverse(opt.begin(), opt.end());
for (ll i = 0; i < opt.size(); i++){
ll v = opt[i].second;
auto exist = vis.find(v);
if (exist == vis.end()){
ll p = visit(v);
vis.insert(v);
if (p + 1 == dist){
step(v, p);
break;
}
else {p = visit(x);}
}
}
return;
}
set<ll> y;
ll find_count(ll x){
y.insert(x);
ll suma = 1;
for (ll i = 0; i < graf[x].size(); i++){
auto exist = y.find(graf[x][i]);
if (exist == y.end()){
suma += find_count(graf[x][i]);
}
}
counts[x] = suma;
return suma;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
vis.clear();
graf.clear();
long long N = F.size()+1;
counts.resize(N+1);
for (ll i = 0; i < N+1; i++){graf.push_back({});}
for (ll i = 0; i < F.size(); i++){
pair p = F[i];
graf[p.first].push_back(p.second);
graf[p.second].push_back(p.first);
}
find_count(curr);
vis.insert(curr);
step(curr, t);
return;
}
