#include <bits/stdc++.h>
std::vector<std::vector<int>> adj;
std::set<int> alr_sent;
int buff_messages = 5;
int send_message(int N, int i, int Pi) {
if (adj.empty()) {
adj.resize(N);
}
adj[i].push_back(Pi);
adj[Pi].push_back(i);
if (i == N - 1) {
std::vector<int> d(N);
auto dfs = [&](auto &&self, int u, int p) -> void {
for (int &i : adj[u]) {
if (i != p) {
d[i] = d[u] + 1;
self(self, i, u);
}
}
};
dfs(dfs, 0, -1);
std::vector<int> p(N);
std::iota(p.begin(), p.end(), 0);
for (int i : alr_sent) {
p.erase(std::find(p.begin(), p.end(), i));
}
int it = std::max_element(d.begin(), d.end()) - d.begin();
return std::find(p.begin(), p.end(), it) - p.begin() + 1;
} else {
if (buff_messages == 0) {
return 0;
}
if (alr_sent.contains(Pi)) {
return 0;
}
if (Pi + 1 > 9997) {
return 0;
}
buff_messages--;
alr_sent.insert(Pi);
return Pi + 1;
}
}
std::pair<int, int> longest_path(std::vector<int> S) {
adj.clear();
const int n = S.size();
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
for (int _ = 0; _ < S.size() - 1; ++_) {
int i = S[_];
if (i == 0) {
continue;
}
p.erase(std::find(p.begin(), p.end(), i - 1));
}
return {0, p[S.back() - 1]};
}
