#include <vector>
#include "incursion.h"
#include <queue>
#include <unordered_set>
using namespace std;
static vector<vector<int>> graf;
static unordered_set<int> vis;
// MARK: compute distances from the safe in assistant’s numbering
vector<int> mark(vector<pair<int,int>> F, int safe) {
int N = (int)F.size() + 1;
graf.assign(N+1, {});
for (auto &e : F) {
graf[e.first].push_back(e.second);
graf[e.second].push_back(e.first);
}
vector<int> depth(N+1, -1);
queue<int> q;
depth[safe] = 0;
q.push(safe);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graf[u]) {
if (depth[v] < 0) {
depth[v] = depth[u] + 1;
q.push(v);
}
}
}
// return depths for rooms 1..N
return vector<int>(depth.begin()+1, depth.end());
}
// LOCATE: recursively descend to the safe, using only visit() queries
static bool step(int x, int dist) {
if (dist == 0)
return true; // we are in the safe
for (int v : graf[x]) {
if (!vis.count(v)) {
vis.insert(v);
int p = visit(v);
if (p < dist && step(v, p))
return true; // found a path
// wrong branch—go back and try next neighbor
visit(x);
}
}
return false;
}
void locate(vector<pair<int,int>> F, int curr, int t) {
int N = (int)F.size() + 1;
graf.assign(N+1, {});
for (auto &e : F) {
graf[e.first].push_back(e.second);
graf[e.second].push_back(e.first);
}
vis.clear();
vis.insert(curr);
step(curr, t);
}
