#include <bits/stdc++.h>
using namespace std;
vector <int> adj[10000];
int d[10000];
int last0, last;
string s = "", s1, s2;
void f( int n ) {
if ( n == 0 ) {
return;
}
while ( n > 0 ) {
s += char( ( n % 2 ) + '0' );
n /= 2;
}
return;
}
int send_message ( int n, int i, int pi ) {
int d1[i + 1];
vector <int> visited( i + 1, false );
queue <int> q;
int dmax = 0;
adj[i].push_back( pi );
adj[pi].push_back( i );
d[i] = d[pi] + 1;
int last1 = last0, last2 = last;
if ( d[i] > d[last0] ) {
last0 = i;
}
d1[last0] = 0;
visited[last0] = true;
q.push( last0 );
while ( q.size() ) {
int x = q.front();
q.pop();
for ( auto y : adj[x] ) {
if ( visited[y] == false ) {
visited[y] = true;
d1[y] = d1[x] + 1;
q.push( y );
if ( d1[y] > dmax ) {
last = y;
dmax = d1[y];
} else if ( d1[y] == dmax and ( y == last1 or y == last2 ) ) {
last = y;
}
}
}
}
if ( i == 9969 ) {
f( last0 );
s1 = s;
s = "";
while ( s1.length() < 15 ) {
s1 += "0";
}
f( last );
s2 = s;
while ( s2.length() < 15 ) {
s2 += "0";
}
} else if ( i > 9969 and i < 9985 ) {
if ( last1 == last0 and last == last2 ) {
return s1[i - 9970] - '0';
} else if ( last1 == last0 ) {
return 2;
} else {
return s1[i - 9970] - '0' + 3;
}
} else if ( i > 9984 ) {
if ( last1 == last0 and last2 == last ) {
return s2[i - 9985] - '0';
} else if ( last2 == last0 ) {
return 2;
} else {
return s2[i - 9985] - '0' + 3;
}
}
return 0;
}
pair <int, int> longest_path ( vector <int> a ) {
pair <int, int> answer = {0, 0};
bool b = false, b1 = false;
int k = 1;
for ( int i = 9970; i < 10000; i++ ) {
if ( i < 9985 ) {
if ( a[i] == 2 ) {
answer.first = i;
b = true;
} else if ( a[i] >= 3 ) {
answer.second = i;
if ( b == false ) {
answer.first += ( a[i] - 3 ) * k;
}
b1 = true;
} else if ( b == false ) {
answer.first += a[i] * k;
}
if ( i == 9984 ) {
k = 1;
} else {
k *= 2;
}
} else {
if ( a[i] == 2 ) {
answer.second = i;
b1 = true;
} else if ( a[i] >= 3 ) {
answer.first = i;
if ( b1 == false ) {
answer.second += ( a[i] - 3 ) * k;
}
} else if ( b1 == false ) {
answer.second += a[i] * k;
}
k *= 2;
}
}
if ( answer.second < answer.first ) {
swap ( answer.first, answer.second );
}
return answer;
}
