#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define Z 9
vector<vector<int>> Tree;
int n;
vector<int> depth;
int turnsLeft;
int stage;
int message;
void init(){
Tree.clear();
Tree.resize(n);
depth.clear();
depth.resize(n);
depth[0]=0;
message=0;
stage=0;
turnsLeft=n-31;
}
int cur;
pair<int,int> furthest(int ind,int par=-1){
pair<int,int> ans= make_pair(0,ind);
for(auto x:Tree[ind]){
if(x==par)continue;
pair<int,int> tmp= furthest(x,ind);
if(tmp.first>ans.first){
ans=tmp;
}
}
ans.first++;
return ans;
}
pair<int,int> diam(){
int ind=0;
int p1= furthest(ind).second;
int p2= furthest(p1).second;
if(p1>p2)swap(p1,p2);
return make_pair(p1,p2);
}
pair<int,int> lans;
void computeNext(){
pair<int,int> ans=diam();
if(stage==0){
stage=1;
message=ans.first*(10001)+ans.second;
turnsLeft=12;
lans=ans;
return;
}
if(stage==1){
int v1=cur-ans.first;
if(ans.first==lans.first)v1=0;
int v2=cur-ans.second;
if(ans.second==lans.second||ans.first==lans.second)v2=0;
lans=ans;
stage=2;
message=v1*(13)+v2;
turnsLeft=4;
}
if(stage==2){
int v1=cur-ans.first;
if(ans.first==lans.first)v1=0;
int v2=cur-ans.second;
if(ans.second==lans.second||ans.first==lans.second)v2=0;
stage=3;
message=v1*(5)+v2;
turnsLeft=2;
lans=ans;
}
if(stage==3){
int v1=cur-ans.first;
if(ans.first==lans.first)v1=0;
int v2=cur-ans.second;
if(ans.second==lans.second||ans.first==lans.second)v2=0;
stage=4;
message=v1*(3)+v2;
turnsLeft=1;
lans=ans;
}
if(stage==4){
turnsLeft=1;
if(ans== make_pair(cur-1,cur)){
message=5;
lans=ans;
return;
}
if(ans.second==cur){
if(ans.first==lans.first) message=4;
else message=3;
lans=ans;
return;
}
if(ans.second==cur-1){if( ans.first==lans.first)message=2;
else message=1; lans=ans;return;}
message=0;
lans=ans;
}
}
int send_message(int N, int i, int Pi) {
n=N;
cur=i;
if(i==1){
init();
}
Tree[Pi].push_back(i);
Tree[i].push_back(Pi);
if(turnsLeft==0){
computeNext();
}
if (turnsLeft){
turnsLeft--;
int res=message%Z;
message/=Z;
return res;
}
}
pair<int, int> longest_path(vector<int> S) {
n=S.size();
message=0;
for(int i=n-19;i>=n-30;i--){
message*=Z;
message+=S[i];
}
vector<int> ans={message%10001,message/10001};
if(ans[0]>ans[1])swap(ans[0],ans[1]);
message=0;
for(int i=n-15;i>n-19;i--){
message*=Z;
message+=S[i];
}
pair<int,int> nans= make_pair(message/13,message%13);
if(nans.first==0)nans.first=ans[0];
if(nans.second==0)nans.second=ans[1];
ans={nans.first,nans.second};
message=0;
for(int i=n-13;i>n-15;i--){
message*=Z;
message+=S[i];
}
nans= make_pair(message/5,message%5);
if(nans.first==0)nans.first=ans[0];
if(nans.second==0)nans.second=ans[1];
ans={nans.first,nans.second};
message=0;
for(int i=n-12;i>n-13;i--){
message*=Z;
message+=S[i];
}
nans= make_pair(message/3,message%3);
if(nans.first==0)nans.first=ans[0];
if(nans.second==0)nans.second=ans[1];
ans={nans.first,nans.second};
for(int i=n-11;i<n;i++){
message=S[i];
if(message==5){
ans={i-1,i};
continue;
}
if(message==4){
ans[1]=i;
continue;
}
if(message==3){
swap(ans[0],ans[1]);
ans[1]=i;
continue;
}
if(message==2){
ans[1]=i-1;
continue;
}
if(message==1){
swap(ans[0],ans[1]);
ans[1]=i-1;
continue;
}
}
return make_pair(ans[0],ans[1]);
}
