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