#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll Nm = 10000; const ll Mm = 28;
const ll INF = 1e8;
vector<ll> fadj[Nm];
ll radj[Nm];
vector<ll> adj[Nm];
pair<ll,vector<ll>> mdist(ll x0) {
vector<ll> cdist(Nm,INF);
cdist[x0]=0;
queue<ll> q0;
q0.push(x0);
while (!q0.empty()) {
ll y = q0.front(); q0.pop();
for (ll z: adj[y]) {
if (cdist[z]==INF) {
cdist[z]=cdist[y]+1;
q0.push(z);
}
}
}
ll cmax = -1; vector<ll> cv;
for (ll x=0;x<Nm;x++) {
if (cdist[x]!=INF) {
if (cdist[x]>=cmax) {
if (cdist[x]>cmax) {
cmax = cdist[x];
cv.clear();
}
cv.push_back(x);
}
}
}
return {cmax,cv};
}
ll MTR = 0;
pair<ll,pii> gld() {
pii pc = {-1,-1};
ll dc = -1;
for (ll x=0;x<Nm;x++) {
auto A0 = mdist(x);
if (A0.first>dc) {
dc = A0.first;
pc = {x,A0.second[0]};
}
}
return {dc,pc};
}
int send_message(int N, int i, int Pi) {
radj[i]=Pi;
fadj[Pi].push_back(i);
adj[Pi].push_back(i);
adj[i].push_back(Pi);
ll dc; pii pc;
if (i==(N-Mm)) {
auto A0 = gld();
dc = A0.first; pc = A0.second;
MTR = ((pc.first)<<14)+pc.second;
}
if (i>=(N-Mm)) {
ll bt = (MTR>>(i-N+Mm))&1;
ll ct = -1;
auto A0 = mdist(i);
ll dn = A0.first;
vector<ll> vc = A0.second;
if (dn<=dc) {
ct = 0;
} else {
dc = dn;
for (ll x: vc) {
if (x==pc.first) {
pc.second = i;
ct = 1;
break;
}
if (x==pc.second) {
pc.first = i;
ct = 2;
break;
}
}
assert(ct!=-1);
}
return (3*bt+ct);
}
return 0;
}
pair<int,int> longest_path(vector<int> S) {
ll N = S.size();
vector<ll> bv,cv;
for (ll i=(N-Mm);i<N;i++) {
ll bt = S[i]/3; ll ct = S[i]%3;
bv.push_back(bt); cv.push_back(ct);
}
pii pc = {0,0};
for (ll i=0;i<14;i++) {
pc.first += ((bv[i])<<i);
pc.second += ((bv[i+14])<<i);
}
for (ll i=(N-Mm);i<N;i++) {
ll i1 = i-(N-Mm);
if (cv[i1]==1) {
pc.second=i;
} else if (cv[i1]==2) {
pc.first=i;
}
}
return pc;
}
