#include <vector>
#include "incursion.h"
#include <cstdio>
using namespace std;
#include <bits/stdc++.h>
vector<int> mark(vector<pair<int, int>> F, int safe) {
int N = F.size()+1;
vector<int>deg(N+1,0);
vector<vector<int>>adj(N+1);
for(auto i:F){
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
deg[i.first]++;
deg[i.second]++;
}
queue<int>Q;
Q.push(safe);
vector<int>vis(N,0);
vis[safe-1] = 2;
int c = 2;
while(Q.size()){
int x = Q.front();
Q.pop();
for(int i:adj[x]){
if(!vis[i-1]){
Q.push(i);
vis[i-1] = c;
}
}
c--;
c+=3;
c%=3;
}
// print(vis);
return vis;
}
// int visit(int c){
//
// }
void locate(vector<pair<int, int>> F, int curr, int t) {
int N = F.size()+1;
vector<int>deg(N+1,0);
vector<vector<int>>adj(N+1);
for(auto i:F){
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
deg[i.first]++;
deg[i.second]++;
}
queue<int>Q;
vector<int>viss(N+1,0);
if(deg[curr] == 1){
t = visit(adj[curr][0]);
curr = adj[curr][0];
}
int c1 = visit(adj[curr][0]);
int c = visit(curr);
int c2 = visit(adj[curr][1]);
int pv = visit(curr);
int cr;
if(c1 == 0 and c == 1 and c2 == 2){
Q.push(c2);
cr = visit(c2);
viss[c] = 1;
viss[c2] = 1;
}
else if(c1 == 1 and c == 2 and c2 == 0){
cr = visit(c2);
Q.push(c2);
viss[c] = 1;
viss[c2] = 1;
}
else if(c1 == 2 and c == 0 and c2 == 1){
cr = visit(c2);
Q.push(c2);
viss[c] = 1;
viss[c2] = 1;
}
else if(c1 == 2 and c == 1 and c2 == 0){
cr = visit(c1);
Q.push(c1);
viss[c] = 1;
viss[c1] = 1;
}
else if(c1 == 1 and c == 0 and c2 == 2){
cr = visit(c1);
Q.push(c1);
viss[c] = 1;
viss[c1] = 1;
}
else if(c1 == 0 and c == 2 and c2 == 1){
cr = visit(c1);
Q.push(c1);
viss[c] = 1;
viss[c1] = 1;
}
int nt;
while(Q.size()){
int x = Q.front();
Q.pop();
for(int i:adj[x]){
if(!viss[i]){
viss[i] = 1;
nt = visit(i);
if(nt == 2 and cr == 2 and pv == 2){
int res = visit(x);
// return;
break;
}
Q.push(i);
pv = cr;
cr = nt;
}
}
}
return;
}
// int main(){
// vector<pair<int,int>>qur = {{1,2},{2,3},{3,4}};
// vector<int>ans = mark(qur,4);
// for(auto i:ans){
// cout<<i<<" ";
// }
// cout<<endl;
// }
