#include "migrations.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e4+5;
int n=1e4-1;
vector<int> stablo[maxn];
int salji[maxn];
int dist[maxn];
void dfs(int gde,int pret,int d){
dist[gde]=d;
for(int x:stablo[gde])
if(x!=pret)
dfs(x,gde,d+1);
}
vector<int> cand;
int getdist(int a,int b){
dfs(a,a,0);
return dist[b];
}
int send_message(int N, int idx, int par) {
if(idx<n-10){
stablo[par].push_back(idx);
stablo[idx].push_back(par);
return 0;
}
if(idx==n-10){
dfs(0,0,0);
int d1=0;
for(int i=0;i<idx;i++)
if(dist[i]>dist[d1])
d1=i;
dfs(d1,d1,0);
int d2=d1;
for(int i=0;i<idx;i++)
if(dist[i]>dist[d2])
d2=i;
cand.push_back(d1);
cand.push_back(d2);
for(int i=n-10;i<n-6;i++){
salji[i]=d1%10+1;
d1/=10;
}
for(int i=n-6;i<n-2;i++){
salji[i]=d2%10+1;
d2/=10;
}
stablo[par].push_back(idx);
stablo[idx].push_back(par);
return salji[idx];
}
if(idx>n-10 and idx<n-2){
stablo[par].push_back(idx);
stablo[idx].push_back(par);
return salji[idx];
}
if(idx==n-2){
for(int i=n-10;i<n-2;i++)
cand.push_back(i);
sort(cand.begin(),cand.end());
int d=0,broj,cnt=0,a,b;
for(int i=0;i<cand.size();i++)
for(int j=i+1;j<cand.size();j++){
cnt++;
int dd=getdist(cand[i],cand[j]);
if(dd>d){
d=dd;
a=cand[i];
b=cand[j];
broj=cnt;
}
}
cand.clear();
cand.push_back(a);
cand.push_back(b);
salji[idx]=broj%10;
salji[idx+1]=broj/10;
stablo[par].push_back(idx);
stablo[idx].push_back(par);
return salji[idx];
}
if(idx==n-1){
stablo[par].push_back(idx);
stablo[idx].push_back(par);
return salji[idx];
}
stablo[par].push_back(idx);
stablo[idx].push_back(par);
for(int i=n-2;i<=n;i++)
cand.push_back(i);
sort(cand.begin(),cand.end());
int d=0,broj,cnt=0;
for(int i=0;i<cand.size();i++)
for(int j=i+1;j<cand.size();j++){
cnt++;
int dd=getdist(cand[i],cand[j]);
if(dd>d){
d=dd;
broj=cnt;
}
}
return broj;
}
std::pair<int, int> longest_path(std::vector<int> S) {
cand.clear();
int a=0,b=0;
for(int i=n-7;i>=n-10;i--){
a=a*10+S[i]-1;
}
for(int i=n-3;i>=n-6;i--)
b=b*10+S[i]-1;
cand.push_back(a);
cand.push_back(b);
for(int i=n-10;i<=n-3;i++)
cand.push_back(i);
sort(cand.begin(),cand.end());
int br=S[n-1]*10+S[n-2];
for(int i=0;i<cand.size();i++)
for(int j=i+1;j<cand.size();j++){
br--;
if(br==0){
a=cand[i];
b=cand[j];
}
}
cand.clear();
cand.push_back(a);
cand.push_back(b);
for(int i=n-2;i<=n;i++)
cand.push_back(i);
sort(cand.begin(),cand.end());
br=S[n];
for(int i=0;i<cand.size();i++)
for(int j=i+1;j<cand.size();j++){
br--;
if(br==0){
a=cand[i];
b=cand[j];
}
}
return {a,b};
}
