#include "migrations.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int par[10005];
int dept[10005];
int a=0,b=0;
int a1=0,b1=0,a2=0,b2=0,a3=0,b3=0;
int encoded1=0,encoded2,encoded3;
int dist(int a,int b)
{
int rez=0;
if(dept[a]<dept[b])
{
swap(a,b);
}
while(dept[a]>dept[b])
{
a=par[a];
rez++;
}
while(a!=b)
{
a=par[a];
b=par[b];
rez+=2;
}
return rez;
}
long long makecode1(int a,int b)
{
return a*10000+b;
}
long long makecode2(int a,int b)
{
vector<pair<int,int>>vec;
vec.push_back({a1,b1});
for(int i=9981; i<=9992; i++)
{
vec.push_back({a1,i});
vec.push_back({b1,i});
}
for(int i=9981; i<=9992; i++)
{
for(int j=i+1; j<=9992; j++)
{
vec.push_back({i,j});
}
}
for(int i=0; i<vec.size(); i++)
{
if(a==vec[i].first && b==vec[i].second)
{
return i;
}
}
}
long long makecode3(int a,int b)
{
vector<pair<int,int>>vec;
vec.push_back({a2,b2});
vec.push_back({a2,9993});
vec.push_back({a2,9994});
vec.push_back({a2,9995});
vec.push_back({b2,9993});
vec.push_back({b2,9994});
vec.push_back({b2,9995});
vec.push_back({9993,9994});
vec.push_back({9993,9995});
vec.push_back({9993,9996});
vec.push_back({9994,9995});
vec.push_back({9994,9996});
vec.push_back({9995,9996});
for(int i=0; i<vec.size(); i++)
{
if(vec[i].first==a && vec[i].second==b)
{
return i;
}
}
}
int pre=0;
int send_message(int N, int i, int Pi)
{
int c,d,e;
c=9996;
d=9997;
e=9998;
if(i==9981)
{
a1=a;
b1=b;
encoded1=makecode1(a1,b1);
}
if(i==9993)
{
a2=a;
b2=b;
encoded2=makecode2(a2,b2);
}
if(i==9996)
{
a3=a;
b3=b;
encoded3=makecode3(a,b);
}
par[i]=Pi;
dept[i]=dept[Pi]+1;
if(dist(a,i)>dist(a,b))
{
a=a;
b=i;
}
if(dist(b,i)>dist(a,b))
{
a=b;
b=i;
}
if(i>=9981 && i<=9992)
{
int retvalue=encoded1%5;
encoded1=encoded1/5;
return retvalue;
}
else if(i>=9993 && i<=9995)
{
int retvalue=encoded2%5;
encoded2=encoded2/5;
return retvalue;
}
else if(i==9996 || i==9997)
{
int retvalue=encoded3%5;
encoded3=encoded3/5;
return retvalue;
}
else if(i==9998)
{
if(a==a3 && (b==b3 || b==c))
{
pre=0;
return 0;
}
if(a==b3 && (b==c || b==d))
{
pre=1;
return 1;
}
if((a==a3 || a==c) && b==d)
{
pre=2;
return 2;
}
if((a==a3 || a==b3) && b==e)
{
pre=3;
return 3;
}
if((a==c || a==d) && b==e)
{
pre=4;
return 4;
}
}
else if(i==9999)
{
int f=9999;
vector<pair<int,int>>vec;
if(pre==0)
{
vec.push_back({a3,b3});
vec.push_back({a3,c});
vec.push_back({a3,f});
vec.push_back({b3,f});
vec.push_back({c,f});
}
else if(pre==1)
{
vec.push_back({b3,c});
vec.push_back({b3,d});
vec.push_back({b3,f});
vec.push_back({c,f});
vec.push_back({d,f});
}
else if(pre==2)
{
vec.push_back({a3,d});
vec.push_back({c,d});
vec.push_back({a3,f});
vec.push_back({c,f});
vec.push_back({d,f});
}
else if(pre==3)
{
vec.push_back({a3,e});
vec.push_back({b3,e});
vec.push_back({a3,f});
vec.push_back({b3,f});
vec.push_back({e,f});
}
else if(pre==4)
{
vec.push_back({c,e});
vec.push_back({d,e});
vec.push_back({c,f});
vec.push_back({d,f});
vec.push_back({e,f});
}
for(int i=0; i<vec.size(); i++)
{
if(vec[i].first==a && vec[i].second==b)
{
return i;
}
}
}
return 0;
}
pair<int,int>getnew1(int a,int b,int code)
{
vector<pair<int,int>>vec;
vec.push_back({a,b});
for(int i=9981; i<=9992; i++)
{
vec.push_back({a,i});
vec.push_back({b,i});
}
for(int i=9981; i<=9992; i++)
{
for(int j=i+1; j<=9992; j++)
{
vec.push_back({i,j});
}
}
return vec[code];
}
pair<int,int> getnew2(int a,int b,int code)
{
vector<pair<int,int>>vec;
vec.push_back({a,b});
vec.push_back({a,9993});
vec.push_back({a,9994});
vec.push_back({a,9995});
vec.push_back({b,9993});
vec.push_back({b,9994});
vec.push_back({b,9995});
vec.push_back({9993,9994});
vec.push_back({9993,9995});
vec.push_back({9993,9996});
vec.push_back({9994,9995});
vec.push_back({9994,9996});
vec.push_back({9995,9996});
return vec[code];
}
std::pair<int, int> longest_path(std::vector<int> S)
{
int pw=1;
long long code=0;
for(int i=9981; i<=9992; i++)
{
code=code+S[i]*pw;
pw=pw*5;
}
a=code/10000;
b=code%10000;
pw=1;
code=0;
for(int i=9993; i<=9995; i++)
{
code=code+S[i]*pw;
pw=pw*5;
}
pair<int,int>rez;
rez=getnew1(a,b,code);
a=rez.first;
b=rez.second;
pw=1;
code=0;
for(int i=9996; i<=9997; i++)
{
code=code+S[i]*pw;
pw=pw*5;
}
rez=getnew2(a,b,code);
a3=rez.first;
b3=rez.second;
pre=S[9998];
int c,d,e;
c=9996;
d=9997;
e=9998;
int f=9999;
vector<pair<int,int>>vec;
if(pre==0)
{
vec.push_back({a3,b3});
vec.push_back({a3,c});
vec.push_back({a3,f});
vec.push_back({b3,f});
vec.push_back({c,f});
}
else if(pre==1)
{
vec.push_back({b3,c});
vec.push_back({b3,d});
vec.push_back({b3,f});
vec.push_back({c,f});
vec.push_back({d,f});
}
else if(pre==2)
{
vec.push_back({a3,d});
vec.push_back({c,d});
vec.push_back({a3,f});
vec.push_back({c,f});
vec.push_back({d,f});
}
else if(pre==3)
{
vec.push_back({a3,e});
vec.push_back({b3,e});
vec.push_back({a3,f});
vec.push_back({b3,f});
vec.push_back({e,f});
}
else if(pre==4)
{
vec.push_back({c,e});
vec.push_back({d,e});
vec.push_back({c,f});
vec.push_back({d,f});
vec.push_back({e,f});
}
return vec[S[f]];
}
