#include <vector>
#include <queue>
#include <utility>
#include "migrations.h"
using namespace std;
// Globals (same behavior as Python globals)
static vector<vector<int>> graph_;
static vector<int> depth_;
// Optional: call this if you want to reuse between runs/tests.
void reset_state() {
graph_.clear();
depth_.clear();
}
// Builds the graph and depths on the fly.
// Returns 1 if i == N-1, else 0 (same as Python).
int send_message(int N, int i, int Pi) {
if (graph_.empty()) {
graph_.assign(N, {});
depth_.assign(N, 0);
}
graph_[Pi].push_back(i);
graph_[i].push_back(Pi);
depth_[i] = depth_[Pi] + 1;
return (i == N - 1) ? 1 : 0;
}
// Finds the two endpoints (u, v) of a longest path (tree diameter).
// Parameter S is unused (kept to match the Python signature).
pair<int,int> longest_path(vector<int> S) {
const int n = static_cast<int>(graph_.size());
if (n == 0) return { -1, -1 };
auto bfs_farthest = [&](int start) -> pair<int, vector<int>> {
vector<int> dist(n, -1);
queue<int> q;
q.push(start);
dist[start] = 0;
int far = start;
while (!q.empty()) {
int cur = q.front(); q.pop();
if (dist[cur] > dist[far]) far = cur;
for (int nei : graph_[cur]) {
if (dist[nei] == -1) {
dist[nei] = dist[cur] + 1;
q.push(nei);
}
}
}
return { far, dist };
};
// First BFS from node 0 to get u
auto [u, dist0] = bfs_farthest(0);
// Second BFS from u to get v
auto [v, distu] = bfs_farthest(u);
return { u, v };
}
