#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
const int N = 5e4 + 5;
vector<int> mark(vector<pair<int, int>> F, int safe) {
vector<int> g[N];
int n = F.size() + 1;
for (auto x : F) {
g[x.first - 1].emplace_back(x.second - 1);
g[x.second - 1].emplace_back(x.first - 1);
}
vector<int> d(n, -1);
safe--;
d[safe] = 0;
queue<int> q;
q.push(safe);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
vector<int> g[N];
for (auto x : F) {
g[x.first].emplace_back(x.second);
g[x.second].emplace_back(x.first);
}
int x = curr;
set<int> vis;
if (t == 0) {
return;
}
vis.insert(x);
if (g[x].size() == 1) {
assert(visit(g[x][0]) == t - 1);
vis.insert(g[x][0]);
x = g[x][0];
} else {
assert(g[x].size() == 2);
int y = visit(g[x][0]);
visit(x);
int z = visit(g[x][1]);
visit(x);
if (y < z) {
assert(visit(g[x][0]) == t - 1);
x = g[x][0];
vis.insert(x);
} else {
assert(visit(g[x][1]) == t - 1);
x = g[x][1];
vis.insert(x);
}
}
t--;
while (t > 0) {
if (g[x].size() == 1) {
// assert(visit(g[x][0]) == t - 1);
vis.insert(g[x][0]);
x = g[x][0];
} else if (g[x].size() == 2) {
if (vis.count(g[x][0])) {
// assert(visit(g[x][1]) == t - 1);
vis.insert(g[x][1]);
x = g[x][1];
} else {
// assert(vis.count(g[x][1]));
// assert(visit(g[x][0]) == t - 1);
vis.insert(g[x][0]);
x = g[x][0];
}
}
t--;
}
return;
}
