#include "migrations.h"
#include <iostream>
#include <vector>
using namespace std;
vector <int> gr[10000];
int dist[10000],X[14],Y[14];
int maxd,curd,x,y,faru;
void dfs(int pu, int u, int d){
curd=max(curd,d);
dist[u]=d;
for (int i=0;i<(int)gr[u].size();i++){
int v=gr[u][i];
if (v!=pu) dfs(u,v,d+1);
}
}
int send_message(int N, int u, int pu) {
int pos;
gr[u].push_back(pu); gr[pu].push_back(u);
if (u<N-28){
return 0;
} else
if (u==N-28){
curd=0; dfs(-1,0,0);
for (int i=0;i<=u;i++) if (dist[i]==curd) { faru=i;break;}
x=faru;
for (int i=0;i<14;i++) X[i]=faru%2, faru=faru/2;
curd=0; dfs(-1,x,0);
for (int i=0;i<=u;i++) if (dist[i]==curd) {faru=i;break;}
y=faru; maxd=curd;
for (int i=0;i<14;i++) Y[i]=faru%2, faru=faru/2;
return X[0];
} else
if (u<N-14) {
pos=u-(N-28); curd=0; dfs(-1,u,0);
if (curd>maxd) {
maxd=curd;
for (int i=0;i<=u;i++)
if (dist[i]==curd && (i==x || i==y)) {faru=i;break;}
if (faru==x) X[pos]+=2,y=u;
else X[pos]=4, x=u;
} else
if (x>0) X[pos]=0;
return X[pos];
} else { //u>=N-14 && u<N
pos=u-(N-14);
curd=0; dfs(-1,u,0);
if (curd>maxd) {
maxd=curd;
for (int i=0;i<=u;i++)
if (dist[i]==curd && (i==x || i==y)) {faru=i;break;}
if (faru==y) Y[pos]+=2,x=u;
else Y[pos]=4, y=u;
} else
if (y>0) Y[pos]=0;
return Y[pos];
}
}
std::pair<int, int> longest_path(std::vector<int> S) {
int n=S.size();
int x=0,y=0,h;
for (int i=n-28;i<n-14;i++)
if (S[i]==4) x=i; else
if (S[i]>1) S[i]-=2,y=i;
for (int i=n-14;i<n;i++)
if (S[i]==4) y=i; else
if (S[i]>1) S[i]-=2,x=i;
if (x==0){
h=1;
for (int i=n-28;i<n-14;i++) x=x+h*S[i], h=h*2;
}
if (y==0){
h=1;
for (int i=n-14;i<n;i++) y=y+h*S[i], h=h*2;
}
pair <int,int> ans=make_pair(x,y);
return ans;
}
/*
30
0 1 2 2 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
*/
