#include <bits/stdc++.h>
#include "incursion.h"
#define f0r(i,n) for(int i = 0;i<n;i++)
#define vi vector<int>
using namespace std;
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
safe--;
int n;
int two;
n = F.size() + 1;
vector<int>dist(n);
dist[safe] = 0;
vector<int>adj[n];
vi deg(n, 0);
vi degcnt(4, 0);
f0r(i, n-1){
adj[--F[i].first].push_back(--F[i].second);
adj[F[i].second].push_back(F[i].first);
deg[F[i].first]++;
deg[F[i].second]++;
}
//f0r(i,n)cout<<deg[i]<<' ';
//cout<<'\n';
f0r(i,n){
if(deg[i] == 2)two = i;
degcnt[deg[i]]++;
}
if(degcnt[3] == 0){
vi col(n, 0);
queue<int>q;
q.push(safe);
vector<bool>vis(n,0);
vis[safe] = 1;
col[safe] = 0;
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(vis[u])continue;
vis[u] = 1;
dist[u] = dist[cur] + 1;
col[u] = (col[cur] + 1) % 3;
q.push(u);
}
}
return col;
}
else{
vi col(n,0);
vi par(n);
par[two] = -1;
queue<int>q;
q.push(two);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(u != par[cur]){
par[u] = cur;
q.push(u);
}
}
}
//f0r(i,n)cout<<par[i]<<' ';
//cout<<'\n';
int now = safe;
while(now != -1){
//cout<<now<<'\n';
col[now] = 1;
now = par[now];
}
//cout<<cur<<'\n';
//cout<<par[cur]<<'\n';
//cout<<par[par[par[cur]]]<<'\n';
return col;
}
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
int x;
vector<int>nxt = {2, 0, 1};
int n = F.size() + 1;
vector<bool>vis(n+1, 0);
vector<int>adj[n+1];
vi deg(n+1);
vi degcnt(4, 0);
f0r(i, n-1){
adj[F[i].first].push_back(F[i].second);
adj[F[i].second].push_back(F[i].first);
deg[F[i].first]++;
deg[F[i].second]++;
}
int two;
for(int i = 1; i<=n; i++){
if(deg[i]==2)two = i;
degcnt[deg[i]]++;
}
if(degcnt[3] == 0){
vis[curr] = 1;
//queue<int>q;
//q.push(curr);
bool found = false;
int col = t;
int cur = curr;
vi cols(n+1, -1);
cols[curr] = t;
while(!found){
bool ok = 0;
for(auto u : adj[cur]){
if(vis[u])continue;
vis[u] = 1;
x = visit(u);
cols[u] = x;
if(x == nxt[cols[cur]]){
cur = u;
ok = 1;
break;
}
else{
visit(cur);
}
}
if(!ok)return;
}
}
else{
vi par(n+1);
par[two] = -1;
vi d(n+1, 0);
queue<int>q;
q.push(two);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(u != par[cur]){
par[u] = cur;
d[u] = d[cur] + 1;
q.push(u);
}
}
}
//for(int i = 1; i<=n; i++)cout<<d[i]<<' ';
//cout<<'\n';
vector<bool>viss(n+1, 0);
vi sts(n+1, 0);
priority_queue<pair<int,int>>pq;
for(int i=1; i<=n;i++){
if(deg[i] == 1){
pq.push({d[i], i});
sts[i] = 1;
viss[i] = 1;
}
}
while(!pq.empty()){
int cur = pq.top().second;
pq.pop();
//cout<<cur<<'\n';
//if(par[cur] != -1)sts[par[cur]] += sts[cur];
if(par[cur] != -1 && !viss[par[cur]]){
viss[par[cur]] = 1;
for(auto u : adj[par[cur]]){
if(u != par[par[cur]]){
sts[par[cur]] += sts[u];
}
}
pq.push({d[par[cur]], par[cur]});
}
}
//for(int i = 1; i<=n; i++)cout<<sts[i]<<' ';
//cout<<'\n';
vi vis(n+1, 0);
int cur = curr;
int col = t;
int x;
vis[cur] = 1;
while(col == 0){
cur = par[cur];
vis[cur] = 1;
x = visit(cur);
col = x;
}
bool found = 0;
while(!found){
vector<pair<int,int>>thing;
for(auto u : adj[cur]){
if(!vis[u] && u != par[cur])thing.push_back({sts[u], u});
}
sort(thing.rbegin(), thing.rend());
bool ok =0;
for(auto u : thing){
x = visit(u.second);
if(x == 0){
visit(cur);
}
else{
cur = u.second;
vis[cur] = 1;
col = x;
ok = 1;
break;
}
}
if(!ok)return;
}
}
}
