#include <bits/stdc++.h>
#include "incursion.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 45000;
vector<vi> edges(N);
vi dist(N,-1);
void dfs(int node,int der = 0) {
if (dist[node] != -1) return;
dist[node] = der;
for (auto it : edges[node]) dfs(it,der+1);
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
int n = 0;
for (int i = 0;i<F.size();i++){
F[i].ff--,F[i].ss--;
if (edges[F[i].ff].empty()) n++;
if (edges[F[i].ss].empty()) n++;
edges[F[i].ff].push_back(F[i].ss);
edges[F[i].ss].push_back(F[i].ff);
}
dfs(safe-1);
dist.resize(n);
edges.resize(n);
return dist;
}
int play(int curr,int t,int par) {
for (auto it : edges[curr]) {
if (it == par) continue;
int x = visit(it+1);
if (x > t) {
//wrong direction
visit(curr+1);
continue;
}
return play(it,x,curr);
}
return curr+1;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
for (auto& it : edges) it.clear();
for (int i = 0;i<F.size();i++){
F[i].ff--,F[i].ss--;
edges[F[i].ff].push_back(F[i].ss);
edges[F[i].ss].push_back(F[i].ff);
}
curr--;
curr = play(curr,t,curr);
}
