#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #ifndef ONLINE_JUDGE
// #include "grader.cpp"
// #endif
const int N = 1e4;
int p[N];
int lst = -1;
vector<int> adj[N];
int dep[N];
int x,y,xx,yy;
int cur = 0;
int bfs(int src){
queue<int> q;
vector<bool> vis(N);
for(int i=0;i<N;i++) dep[i] = 0;
q.push(src);
vis[src] = 1;
while(q.size()){
int node = q.front(); q.pop();
for(auto ch : adj[node]){
if(vis[ch]) continue;
q.push(ch);
vis[ch] = 1;
dep[ch] = dep[node] + 1;
}
}
pair<int,int> mx{-1,0};
for(int j=0;j<N;j++) {
if(dep[j] > mx.first) mx = {dep[j] , j};
else if(dep[j] == mx.first && (j == xx || j == yy)) mx = {dep[j] , j};
else if(dep[j] == mx.first && (j == cur)) mx = {dep[j] , j};
}
return mx.second;
}
pair<int,int> calc(){
int tmp = bfs(0);
pair<int,int> p{tmp,bfs(tmp)};
if(tmp == yy || p.second == xx) swap(p.first,p.second);
return p;
}
int changed_x = 0 , changed_y = 0;
int send_message(int n, int i, int Pi) {
adj[i].push_back(Pi);
adj[Pi].push_back(i);
vector<ll> powe(8);
powe[0] = 1;
for(int j=1;j<=7;j++) powe[j] = powe[j-1] * 4;
// cout<<i<<": "<<x<<' '<<y<<endl;
if(i >= n - 21){
int it = i - (n-21);
cur = i;
auto [xx_,yy_] = calc();
xx = xx_;
yy = yy_;
// cout<<i<<" -> "<<xx<<' '<<yy<<endl;
if(it < 8) y = yy;
if(it < 7){
if(xx == x) return (x / powe[it]) % 4;
else return x = xx , 4;
}
else {
it -= 7;
if(it % 2 == 0){
if(y == yy) return (y / powe[it>>1]) % 4;
else return y = yy , 4;
}
else {
if(xx == i) return x = xx, 0;
else if(xx == i-1 && yy != i) return x = xx , 1;
else if(xx == i-1 && yy == i) return x = xx , y = yy , 2;
else if(yy != i) return 3;
else if(yy == i) return y = yy , 4;
}
}
}
else {
auto [xx_,yy_] = calc();
xx = xx_;
yy = yy_;
x = xx , y = yy;
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
vector<ll> powe(8);
powe[0] = 1;
for(int j=1;j<=7;j++) powe[j] = powe[j-1] * 4;
int n = N;
int x = 0 , y = 0;
bool changed_x = 0 , changed_y = 0;
for(int i=n-21;i<n;i++){
int it = i - (n-21);
if(it < 7){
if(S[i] == 4) changed_x = 1 , x = i;
else if(!changed_x){
x += powe[it] * S[i];
}
}
else {
it -= 7;
if(it % 2 == 0){
if(S[i] == 4) changed_y = 1 , y = i;
else if(!changed_y) y += powe[it>>1] * S[i];
}
else {
if(S[i] == 0) x = i;
else if(S[i] == 1) x = i - 1;
else if(S[i] == 2) x = i - 1 , y = i , changed_y = 1;
else if(S[i] == 3) continue;
else y = i , changed_y = 1;
}
}
}
// cout<<x<<' '<<y<<endl;
// bfs(x);
// cout<<dep[y]<<endl;
return {x,y};
}
