#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10009;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
int P[maxn] , jump[maxn] , dep[maxn] , jsiz[maxn] , dpth[maxn];
vector <int > s[maxn];
pii maxi[maxn][3];
pii aktp;
int aktlen = 0 ;
bool comp(pii p1 , pii p2)
{
return p1 > p2;
}
void DFS(int v)
{
dpth[v] = 0;
maxi[v][0] = {0, v};
maxi[v][1] = {0, v};
maxi[v][2] = {0, v};
for(auto p : s[v])
{
DFS(p);
maxi[v][2] = {dpth[p]+1 , maxi[p][0].nd};
sort(maxi[v] , maxi[v]+3 , comp);
dpth[v] = max(dpth[v],dpth[p]+1);
}
int A = maxi[v][0].st + maxi[v][1].st;
if(A > aktlen)
{
aktlen = A;
aktp = {maxi[v][0].nd , maxi[v][1].nd};
}
}
int find(int x, int w)
{
while(w)
{
if(jsiz[x] <= w)
{
w -= jsiz[x];
x = jump[x];
}
else
{
w--;
x = P[x];
}
}
return x;
}
int dis(int a ,int b)
{
if(dep[a] > dep[b])swap(a,b);
int az = a , bz = b;
b = find(b , dep[b]-dep[a]);
while(a != b)
{
if(jump[a] == jump[b])
{
a = P[a];
b = P[b];
}
else
{
a = jump[a];
b = jump[b];
}
}
return dep[az]+dep[bz]-2*dep[a];
}
int send_message(int N, int i, int Pi)
{
if(i == 1)
{
for(int j = 0 ;j <= N ; j++)
{
P[j] = 0;
s[j].clear();
for(int k = 0; k < 3 ; k++)maxi[j][k].st = 0;
for(int k = 0 ;k < 3 ; k++)maxi[j][k].nd = 0;
jump[j] = 0;
dep[j] = 0;
}
}
P[i] = Pi;
dep[i] = dep[Pi]+1;
s[Pi].push_back(i);
if(jsiz[Pi] == jsiz[jump[Pi]])
{
jsiz[i] = 2*jsiz[Pi]+1;
jump[i] = jump[jump[Pi]];
}
else
{
jsiz[i] = 1;
jump[i] = Pi;
}
if(i == (N-1)-27)
{
aktp = {0,0}; aktlen = 0;
DFS(0);
}
if(i >= (N-1)-27)
{
pii p1 = aktp , p2 = aktp;
p1.st = i;
p2.nd = i;
int Z = 0;
if(dis(p1.st , p1.nd) > dis(aktp.st , aktp.nd))
{
aktp = p1;
Z = 1;
}
if(dis(p2.st , p2.nd) > dis(aktp.st , aktp.nd))
{
aktp = p2;
Z = 2;
}
if(i < (N-1)-13)
{
int B = i-((N-1)-27);
if(Z == 1)return 4;
int V = 0;
if(aktp.st&(1<<B))V = 1;
if(Z == 2)V += 2;
return V;
}
else
{
int B = i-((N-1)-13);
if(Z == 2)return 4;
int V = 0;
if(aktp.nd&(1<<B))V = 1;
if(Z == 1)V += 2;
return V;
}
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S)
{
int N = S.size();
int A = 0 , B = 0 ;
bool czyzA = 0 , czyzB = 0;
for(int i = N-1-27 ; i < N-1-13 ; i++)
{
if(S[i] == 4)
{
czyzA = 1;
A = i;
continue;
}
if(S[i] > 1)
{
czyzB = 1;
B = i;
}
if(!czyzA)
{
if(S[i]%2)A += (1<<(i-(N-1-27)));
}
}
for(int i = N-1-13 ; i <= N-1 ; i++)
{
if(S[i] == 4)
{
czyzB = 1;
B = i;
continue;
}
if(S[i] > 1)
{
czyzA = 1;
A = i;
}
if(!czyzB)
{
if(S[i]%2)B += (1<<(i-(N-1-13)));
}
}
return {A,B};
}
/*
45
0 1 2 2 3 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/
