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