#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 45005;
vector<int> adj[MAXN];
int marc[MAXN];
void dfs(int s, int p){
for(int viz : adj[s])
if(viz != p){
marc[viz] = (marc[s]+1)%3;
dfs(viz,s);
}
}
vector<int> mark(vector<pair<int, int>> f, int safe) {
int n = 0;
for(int i = 0; i < sz(f); i++){
adj[ f[i].fi ].push_back( f[i].sc );
adj[ f[i].sc ].push_back( f[i].fi );
n = max( {n, f[i].fi, f[i].sc });
}
dfs(safe,0);
vector<int> ans(n);
for(int i = 1; i <= n; i++){
ans[i-1] = marc[i];
adj[i].clear(); marc[i] = 0;
}
return ans;
}
void locate(vector<pair<int, int>> f, int ini, int t) {
for(int i = 0; i < sz(f); i++){
adj[ f[i].fi ].push_back( f[i].sc );
adj[ f[i].sc ].push_back( f[i].fi );
}
marc[ ini ] = t;
int cur = adj[ini][0];
marc[ cur ] = visit( cur );
if( marc[cur] != (marc[ini]-1 +3)%3 ){
visit( ini );
if(sz( adj[ini] ) == 1)return;
cur = adj[ini][1];
marc[ cur ] = visit( cur );
if(marc[cur] != (marc[ini]-1 +3)%3 ){
visit(ini);
if(sz( adj[ini] ) == 2)return;
cur = adj[ini][2];
marc[ cur ] = (marc[ini]-1 +3)%3;
}
}
int lst = ini;
while(1){
int nxt = -1;
for(int viz : adj[cur])
if(viz != lst){ nxt = viz; break; }
if(nxt == -1){
if(marc[cur] == 2)visit(lst);
return;
}
marc[ nxt ] = visit( nxt );
if(marc[ nxt ] == (marc[cur]-1 +3)%3){
lst = cur; cur = nxt;
}else if(marc[ nxt ] == marc[cur]){
visit(lst);
return;
}else{
visit(cur);
int mudou = 0;
for(int viz : adj[cur])
if(viz != lst && viz != nxt){lst = cur; cur = viz; mudou = 1; }
if(!mudou)return;
}
}
}
