// #ifndef __TASK_CPP
// #define __TASK_CPP
#include <vector>
#include <algorithm>
#include <cassert>
#include <math.h>
using namespace std;
constexpr int N = 1e4;
constexpr int logN = static_cast<int>(log(N));
constexpr int NUM_TRANSMITTER = 9;
pair<int, int> maxopt = {0, 0};
int depth[N] = {0};
int up[N][logN + 1];
const static int c[NUM_TRANSMITTER + 1] = {0,
181, 30, 6, 1, 1, 2, 1, 1, 1
};
const static int l[NUM_TRANSMITTER + 1] = {9842,
440, 70, 20, 5, 2, 4, 5, 2, 1
};
const static int r[NUM_TRANSMITTER + 1] = {10146,
715, 95, 25, 26, 27, 5, 2, 3, 1
};
const static int il[NUM_TRANSMITTER + 1] = {0,
38, 11, 5, 5, 5, 1, 1, 5, 2
};
const static int ir[NUM_TRANSMITTER + 1] = {0,
19, 11, 5, 1, 1, 9, 5, 1, 3
};
int checkpoint[NUM_TRANSMITTER + 1];
int diameter;
int L, R;
vector<int> Lposs, Rposs;
inline long long ceildiv(long long a, long long b) {
return (a + b - 1) / b;
}
void init() {
diameter = 0;
L = 0, R = 0;
maxopt = {0, 0};
depth[0] = 0;
int Nstart = N + 1;
for (int i = 1; i <= NUM_TRANSMITTER; i++) {
Nstart -= c[i];
}
Lposs = Rposs = {0};
}
int lca(int u, int v) {
if (u == -1) return v;
if (v == -1) return u;
if (depth[u] < depth[v]) swap(u, v);
for (int i = logN; i >= 0; i--) {
if (depth[u] - (1 << i) >= depth[v]) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = logN; i >= 0; i--) {
if (up[u][i] == up[v][i]) continue;
u = up[u][i];
v = up[v][i];
}
return up[u][0];
}
int distance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int send_message(int n, int i, int p) {
if (i == 1) init();
depth[i] = depth[p] + 1;
up[i][0] = p;
for (int j = 0; j < logN; j++) {
up[i][j + 1] = up[up[i][j]][j];
}
if (distance(i, L) > diameter) {
diameter = distance(i, L);
R = i;
// cout << "!!!!!!!!! R-diameter has changed! to " << L << ", " << i << " (= " << diameter << ")" << endl;
} else if (distance(i, R) > diameter) {
diameter = distance(i, R);
L = i;
// cout << "!!!!!!!!! L-diameter has changed! to " << i << ", " << R << " (= " << diameter << ")" << endl;
}
Lposs.push_back(i);
Rposs.push_back(i);
int skipped = 0, transmitter;
for (transmitter = NUM_TRANSMITTER; transmitter; transmitter--) {
skipped += c[transmitter];
if (i >= N - skipped) break;
}
if (transmitter == 0) {
return 0;
}
if (i == N - skipped) {
int lpos = lower_bound(Lposs.begin(), Lposs.end(), L) - Lposs.begin();
int rpos = lower_bound(Rposs.begin(), Rposs.end(), R) - Rposs.begin();
// cout << "Lposs = " << Lposs.size() << endl;
// cout << "Rposs = " << Rposs.size() << endl;
int newLposs = l[transmitter];
int newRposs = r[transmitter];
int ldiv = ceildiv(Lposs.size(), il[transmitter]);
int rdiv = ceildiv(Rposs.size(), ir[transmitter]);
int lsent = lpos / ldiv;
int rsent = rpos / rdiv;
checkpoint[transmitter] = lsent * ir[transmitter] + rsent;
// cout << "hi " << transmitter << ": " << rsent * ir[transmitter] << ' ' << min<size_t>(Rposs.size(), (rsent + 1) * ir[transmitter]) << endl;
// cout << "transmitter #" << transmitter << " sent: " << checkpoint[transmitter] << ' ' << lsent << ' ' << rsent << endl;
// cout << i << endl;
Lposs = vector<int>(Lposs.begin() + lsent * ldiv, min(Lposs.end(), Lposs.begin() + (lsent + 1) * ldiv));
Rposs = vector<int>(Rposs.begin() + rsent * rdiv, min(Rposs.end(), Rposs.begin() + (rsent + 1) * rdiv));
}
if (i == N - skipped + checkpoint[transmitter] / 4) {
return 1 + (checkpoint[transmitter] & 3);
}
return 0;
}
pair<int, int> longest_path(vector<int> S) {
init();
int skipped = 0;
for (int transmitter = NUM_TRANSMITTER; transmitter; transmitter--) {
skipped += c[transmitter];
}
int last = 1;
for (int transmitter = 1; transmitter <= NUM_TRANSMITTER; transmitter++) {
for (int i = last; i <= N - skipped; i++) {
Lposs.push_back(i);
}
for (int i = last; i <= N - skipped; i++) {
Rposs.push_back(i);
}
last = N - skipped + 1;
int msg = 4 * c[transmitter];
for (int i = N - skipped; i < N - skipped + c[transmitter]; i++) {
if (S[i]) {
msg = (i - (N - skipped)) * 4 + (S[i] - 1);
break;
}
}
// cout << "there were " << Lposs.size() << " * " << Rposs.size() << " posibilies" << endl;
int newLposs = l[transmitter];
int newRposs = r[transmitter];
int lsent = msg / ir[transmitter];
int rsent = msg % ir[transmitter];
int ldiv = ceildiv(Lposs.size(), il[transmitter]);
int rdiv = ceildiv(Rposs.size(), ir[transmitter]);
// cout << "transmitter #" << transmitter << " revce: " << msg << ' ' << lsent << ' ' << rsent << endl;
Lposs = vector<int>(Lposs.begin() + lsent * ldiv, min(Lposs.end(), Lposs.begin() + (lsent + 1) * ldiv));
Rposs = vector<int>(Rposs.begin() + rsent * rdiv, min(Rposs.end(), Rposs.begin() + (rsent + 1) * rdiv));
skipped -= c[transmitter];
}
assert(Lposs.size() == 1);
assert(Rposs.size() == 1);
return {Lposs[0], Rposs[0]};
}
// #include "IOI25_migrations_gen2.cpp"
// #endif
