#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
/*
Unambiguous low-Z protocol (Z ≤ 3):
Tail-window streaming (W = 24):
- At i == N-W: send 0 (RESET marker; inside the tail window only)
- For i in (N-W+1) .. (N-1):
* Maintain online diameter endpoints (A,B) via LCA.
* If (A,B) changed since last emitted symbol -> send 0 (RESET) and restart stream.
* Else emit base-3 digits (mapped as out = digit+1 in {1,2,3}) interleaved LSB-first:
u0, v0, u1, v1, ..., u8, v8 (18 digits total; 9 per index as 3^9 >= 10000)
After 18 digits are sent, emit padding value '1' (digit 0) for the rest of the window.
- Outside the window: always return 0 (no message).
Museum:
- In the last W positions, find the LAST 0 (reset). Then read the FIRST 18 nonzero symbols
after it, map to digits (value-1), and reconstruct U, V from interleaved base-3 LSB-first.
*/
namespace {
// per-test state
bool inited = false;
int Nglob = 0, LOGv = 0;
const int W = 24; // tail window size: 1 reset + 18 digits + slack
int tailStart = 1;
// tree lifting
vector<int> depth;
vector<vector<int>> up;
// diameter tracking
int A = 0, B = 0, D = 0;
// streaming state
bool streaming = false;
int stream_pos = -1; // 0..17 for the 18 digits; >=18 means padding
int lastA = 0, lastB = 0;
// base-3 powers up to 3^9
int pow3[10];
inline void reset_test(int N){
inited = true;
Nglob = N;
LOGv = 0; while ((1<<LOGv) <= max(1, Nglob)) ++LOGv;
depth.assign(Nglob, 0);
up.assign(Nglob, vector<int>(LOGv, 0));
for (int k=0;k<LOGv;++k) up[0][k] = 0;
A = B = 0; D = 0;
tailStart = max(1, Nglob - W);
streaming = false;
stream_pos = -1;
lastA = lastB = 0;
pow3[0] = 1;
for (int i=1;i<10;++i) pow3[i] = pow3[i-1] * 3;
}
inline int lca(int u, int v){
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k=0; diff; ++k, diff >>= 1) if (diff & 1) u = up[u][k];
if (u == v) return u;
for (int k=LOGv-1; k>=0; --k) if (up[u][k] != up[v][k]){
u = up[u][k]; v = up[v][k];
}
return up[u][0];
}
inline int dist(int u, int v){
int w = lca(u, v);
return depth[u] + depth[v] - 2*depth[w];
}
inline int get_digit_base3(int x, int d){ // d-th digit (LSB-first) in base-3
// x / 3^d % 3
return (x / pow3[d]) % 3;
}
}
int send_message(int N, int i, int Pi){
if (!inited || i == 1) reset_test(N);
// build lifting for node i
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int k=1; k<LOGv; ++k) up[i][k] = up[ up[i][k-1] ][k-1];
// online diameter update
int dA = dist(i, A), dB = dist(i, B);
if (dA > D){ B = i; D = dA; }
else if (dB > D){ A = i; D = dB; }
int out = 0;
if (i == tailStart){
// start of tail window → RESET
out = 0; // reset marker
streaming = false;
stream_pos = -1;
lastA = A; lastB = B;
} else if (i > tailStart){
bool changed = (A != lastA) || (B != lastB);
if (changed){
// reset and restart for new endpoints
out = 0;
streaming = false;
stream_pos = -1;
lastA = A; lastB = B;
} else {
if (!streaming){ streaming = true; stream_pos = 0; }
if (stream_pos < 18){
// interleave U and V base-3 digits: u0,v0,u1,v1,...,u8,v8
int which = stream_pos;
int digit;
if ((which & 1) == 0){ // even → U
int du = which/2;
digit = get_digit_base3(A, du);
} else { // odd → V
int dv = which/2;
digit = get_digit_base3(B, dv);
}
out = digit + 1; // 1..3
++stream_pos;
} else {
// padding: keep Z low and avoid new resets
out = 1; // digit 0
}
}
} else {
// outside tail window: silent
out = 0;
}
return out; // 0..3 (0 used only as reset inside the tail)
}
std::pair<int,int> longest_path(std::vector<int> S){
int N = (int)S.size();
const int W = 24;
int tailStart = max(1, N - W);
// Find last RESET (0) inside the tail window
int lastReset = -1;
for (int i = N-1; i >= tailStart; --i){
if (S[i] == 0){ lastReset = i; break; }
}
if (lastReset == -1){
// Fallback: no reset found (shouldn't happen) → return a safe default
return {0, 0};
}
// Collect the FIRST 18 nonzero digits after lastReset
vector<int> digs;
digs.reserve(18);
for (int i = lastReset + 1; i < N && (int)digs.size() < 18; ++i){
if (S[i] >= 1 && S[i] <= 3) digs.push_back(S[i] - 1); // map to 0..2
// ignore any accidental values outside {1,2,3}
}
while ((int)digs.size() < 18) digs.push_back(0); // pad if tiny N
// Reconstruct U and V from interleaved base-3 digits (LSB-first)
int pow3[10]; pow3[0] = 1; for (int i=1;i<10;++i) pow3[i] = pow3[i-1]*3;
int U = 0, V = 0;
for (int pos = 0; pos < 18; ++pos){
int d = digs[pos];
if ((pos & 1) == 0){ // U digit
int k = pos/2;
U += d * pow3[k];
} else { // V digit
int k = pos/2;
V += d * pow3[k];
}
}
// Clamp to [0, N-1] just in case
if (U >= N) U = N - 1;
if (V >= N) V = N - 1;
return {U, V};
}
