#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
const int N=10000;
vector<vector<int>> g(N);
pair<int,pair<int,int>> bfs(vector<vector<int>>& g){
int n=g.size();
vector<int> dist(n,-1);
queue<int> q;
q.push(0);
dist[0]=0;
while(!q.empty()){
int v=q.front();q.pop();
for(int u:g[v]){
if(dist[u]==-1){
dist[u]=dist[v]+1;
q.push(u);
}
}
}
int start=1,mx=0;
for(int i=0;i<n;i++){
if(dist[i]>mx){
mx=dist[i];
start=i;
}
}
fill(dist.begin(),dist.end(),-1);
q.push(start);
dist[start]=0;
while(!q.empty()){
int v=q.front();
q.pop();
for(int u:g[v]){
if(dist[u]==-1){
dist[u]=dist[v]+1;
q.push(u);
}
}
}
int en=start;
mx=0;
for(int i=0;i<n;i++){
if(dist[i]>mx){
mx=dist[i];
en=i;
}
}
return make_pair(mx,make_pair(start,en));
}
int send_message(int N,int i,int P);
pair<int,int> longest_path(vector<int> S);
int st=0,finish=0;
int send_message(int N,int i,int P){
g[i].pb(P);
g[P].pb(i);
if(!(N-5<=i&&i<=N-1)) return 0;
if(i==N-5) return N;
if(i==N-4){
auto ans=bfs(g);
return ans.ff;
}if(i==N-3){
auto ans=bfs(g);
st=min(ans.ss.ff,ans.ss.ss);
return st+10000;
}if(i==N-2){
auto ans=bfs(g);
finish=max(ans.ss.ss,ans.ss.ff);
return finish;
}if(i==N-1){
auto ans=bfs(g);
int add=0;
if(st!=min(ans.ss.ff,ans.ss.ss)){
add+=10;
}
if(finish!=max(ans.ss.ss,ans.ss.ff)) add+=20;
return ans.ff+add;
}
}
pair<int,int> longest_path(vector<int> S){
int n=S[0];
int a=S[1],b=S[2]-10000,c=S[3],d=S[4];
//cout<<n<<' '<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
if(d-a>=30) return {c,n-1};
if(d-a>=20) return {b,n-1};
if(d-a>=10) return {c,n-1};
if(d==a) return {min(b,c),max(b,c)};
if(d==a+1) return {min(b,c),max(b,c)};
return {min(b,c),max(b,c)};
}
