#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 dist[MAXN];
void dfs(int s, int p){
for(int viz : adj[s])
if(viz != p){
dist[viz] = dist[s]+1;
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] = dist[i];
adj[i].clear(); dist[i] = 0;
}
return ans;
}
void locate(vector<pair<int, int>> f, int ini, int t) {
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 });
}
if(t == 0)return;
dist[ini] = t;
int cur = adj[ini][0];
dist[cur] = visit(cur);
if(dist[cur] != dist[ini]-1){
visit(ini);
cur = adj[ini][1];
dist[cur] = visit(cur);
if(dist[cur] != dist[ini]-1){
visit(ini);
cur = adj[ini][2];
dist[cur] = visit(cur);
}
}
int lst = ini;
while(1){
if(dist[cur] == 0)return;
int nxt = -1;
for(int viz : adj[cur])
if(viz != lst){nxt = viz; break;}
dist[ nxt ] = visit(nxt);
if(dist[nxt] == dist[cur]-1){ lst = cur; cur = nxt; }
else{
visit(cur);
int nxt2 = -1;
for(int viz : adj[cur])
if(viz != lst && viz != nxt){nxt2 = viz; break;}
dist[nxt2] = visit(nxt2);
lst = cur; cur = nxt2;
}
}
}
