#include <bits/stdc++.h>
using namespace std;
vector <int> v[20001];
#include <bits/stdc++.h>
using namespace std;
int bfs(int node, int mx){
int n=mx;
vector<int> dist(n, -1);
queue<int> q;
dist[node]=0;
q.push(node);
int f=node;
while (!q.empty()) {
int t=q.front();
q.pop();
for (int i=0; i<v[t].size(); i++) {
int to=v[t][i];
if (dist[to]==-1) {
dist[to]=dist[t]+1;
q.push(to);
if (dist[to]>dist[f])
f=to;
}}}
return f-1872;
}
int send_message(int N, int i, int Pi){
if (i!=N-1){
v[i].push_back(Pi);
v[Pi].push_back(i);
return 0;
}
else{
v[i].push_back(Pi);
v[Pi].push_back(i);
int T=bfs(0,N);
return (T);
}
}
std::pair<int,int> longest_path(std::vector<int> S){
return {0,S[S.size()-1]+1872};
}
