#include "migrations.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Aritro Sarkar
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
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=0;
for(int i=0;i<n;i++) if(dist[i] > dist[start]) start=i;
fill(dist.begin(),dist.end(),-1);
queue<int> q2;
q2.push(start);
dist[start]=0;
while(!q2.empty()){
int v=q2.front(); q2.pop();
for(int u:g[v]){
if(dist[u]==-1){
dist[u]=dist[v]+1;
q2.push(u);
}
}
}
int en=start;
for(int i=0;i<n;i++) if(dist[i]>dist[en]) en=i;
return {dist[en],{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 new_st=0,newer_st=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+1;
}if(i==N-2){
auto ans=bfs(g);
new_st==min(ans.ss.ff,ans.ss.ss);
finish=max(ans.ss.ss,ans.ss.ff);
return finish+1;
}if(i==N-1){
auto ans=bfs(g);
newer_st=min(ans.ss.ff,ans.ss.ss);
int add=0;
if(finish!=max(ans.ss.ff,ans.ss.ss)) add+=10;
if(st!=min(ans.ss.ss,ans.ss.ff)){
if(new_st!=st) add+=50;
else if(newer_st!=st) add+=20;
}
return ans.ff+add;
}
}
pair<int,int> longest_path(vector<int> S){
if(S.size()<5) return {0,0};
int n=S[N-5];
int a=S[n-4],b=S[n-3]-1,c=S[n-2]-1,d=S[n-1];
if(d-a>=60) return {n-2,n-1};
if(d-a>=50) return {n-2,c};
if(d-a>=30) return {n-1,n-1};
if(d-a>=20) return {n-1,c};
if(d-a>=10) return {b,n-1};
return {b,c};
}
