#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 dfs(int u, int p, vector<vector<int>> &g, vector<int> &fa) {
for (int v : g[u]) {
if (v != p) {
fa[v] = u;
dfs(v, u, g, fa);
}
}
}
void locate(vector<pair<int, int>> F, int curr, int t) {
vector<vector<int>> g;
int n = F.size() + 1;
g.resize(N);
int deg[N];
memset(deg, 0, sizeof(deg));
for (auto x : F) {
g[x.first].emplace_back(x.second);
g[x.second].emplace_back(x.first);
deg[x.first]++;
deg[x.second]++;
}
bool f = true;
for (int i = 1; i <= n; i++) {
f &= (deg[i] < 3);
}
if (f) {
int x = curr;
set<int> vis;
if (t == 0) {
return;
}
vis.insert(x);
if (g[x].size() == 1) {
vis.insert(g[x][0]);
x = g[x][0];
} else {
int y = visit(g[x][0]);
visit(x);
int z = visit(g[x][1]);
visit(x);
if (y < z) {
visit(g[x][0]);
x = g[x][0];
vis.insert(x);
} else {
visit(g[x][1]);
x = g[x][1];
vis.insert(x);
}
}
t--;
while (t > 0) {
if (g[x].size() == 1) {
visit(g[x][0]);
vis.insert(g[x][0]);
x = g[x][0];
} else if (g[x].size() == 2) {
if (vis.count(g[x][0])) {
visit(g[x][1]);
vis.insert(g[x][1]);
x = g[x][1];
} else {
visit(g[x][0]);
vis.insert(g[x][0]);
x = g[x][0];
}
}
t--;
}
return;
}
vector<int> fa(N, 0);
int root;
// assert(count(deg + 1, deg + n + 1, 2) == 1);
for (int i = 1; i <= n; i++) {
if (deg[i] == 2) {
root = i;
}
}
dfs(root, root, g, fa);
if (t == 0) {
return;
}
int x = curr;
set<int> vis;
vis.insert(x);
while (x != root) {
if (visit(fa[x]) < t) {
x = fa[x];
vis.insert(x);
t--;
} else {
visit(x);
break;
}
}
while (t > 0) {
vector<int> cnd;
for (int y : g[x]) {
if (!vis.count(y)) {
cnd.emplace_back(y);
}
}
if (visit(cnd[0]) < t) {
t--;
x = cnd[0];
vis.insert(x);
} else {
visit(x);
visit(cnd[1]);
t--;
x = cnd[1];
vis.insert(x);
}
}
return;
}
