#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
/*
Goal: Z ≤ 4, M ≈ 15–20, correctness guaranteed.
Protocol (tail-window streaming):
- Reserve a window of size W at the end (W >= 1 + 14 = 15; we use W = 20 for slack).
- At i == N - W : send RESET (= 4).
- For i in (N - W + 1) .. (N - 1):
* Track online diameter endpoints (A,B).
* If (A,B) changed since the last emitted digit → send RESET (=4), mark a new stream start.
* Else emit the next base-4 digit of U and V interleaved, LSB-first:
order: u0, v0, u1, v1, ..., u6, v6 (14 digits total)
The digit positions wrap if the stream restarts.
- Outside the window: send 0.
Museum decoding:
- From the tail window, take digits after the LAST reset (value 4).
- Read the LAST 14 digits after that reset; interleaved LSB-first, reconstruct U and V.
- If there are fewer than 14 digits (very small N), pad missing high digits with 0.
*/
namespace {
// globals per test
bool inited = false;
int Nglob = 0, LOGv = 0;
const int W = 20; // tail window size (tune: 20–32)
int startTail = 1; // N - W
// tree lifting
vector<int> depth;
vector<vector<int>> up;
// diameter state
int A = 0, B = 0, D = 0;
// streaming state
int stream_pos = -1; // -1 means not streaming yet; else 0..13
int lastA = 0, lastB = 0; // to detect changes
bool streaming = false;
// helpers
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;
startTail = max(1, Nglob - W);
stream_pos = -1;
lastA = lastB = 0;
streaming = false;
}
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_base4(int x, int d){ // d-th digit, LSB-first
return (x >> (2*d)) & 3; // since base-4 digit = 2 bits
}
}
int send_message(int N, int i, int Pi){
if (!inited || i==1) reset_test(N);
// build lifting
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];
// update diameter
int dA = dist(i,A), dB = dist(i,B);
if (dA > D){ B = i; D = dA; }
else if (dB > D){ A = i; D = dB; }
// default silent
int out = 0;
if (i == N - W){
// force a reset: start of tail window
out = 4; // RESET marker (Z ≤ 4 holds)
streaming = false;
stream_pos = -1;
lastA = A; lastB = B;
} else if (i > N - W){
// inside tail window
bool changed = (A != lastA) || (B != lastB);
if (changed){
out = 4; // RESET
streaming = false;
stream_pos = -1;
lastA = A; lastB = B;
} else {
// continue / start streaming digits for (A,B)
if (!streaming){ streaming = true; stream_pos = 0; }
int digit;
if (stream_pos < 14){
// interleaved u0,v0,u1,v1,...
int which = stream_pos;
if (which % 2 == 0){
int du = which/2;
digit = get_digit_base4(A, du);
} else {
int dv = which/2;
digit = get_digit_base4(B, dv);
}
} else {
// extra digits (if any) harmless; send 0 to stay in Z ≤ 4
digit = 0;
}
out = digit + 1; // map {0,1,2,3} -> {1,2,3,4}
++stream_pos;
}
}
return out; // 0 outside window; 1..4 inside
}
std::pair<int,int> longest_path(std::vector<int> S){
int N = (int)S.size();
int tailStart = max(1, N - 20); // must match W in send_message
// Find the last reset (=4) in the tail window
int lastReset = -1;
for (int i = N-1; i >= tailStart; --i){
if (S[i] == 4) { lastReset = i; break; }
}
// Collect digits after last reset
vector<int> digs; digs.reserve(20);
for (int i = max(tailStart, lastReset+1); i < N; ++i){
int v = S[i];
if (v >= 1 && v <= 4) digs.push_back(v-1); // base-4 digit
}
// We need the last 14 digits after the last reset.
while ((int)digs.size() < 14) digs.push_back(0); // pad if tiny N
// Take the last 14
vector<int> last14(digs.end()-14, digs.end());
// Reconstruct A and B from interleaved LSB-first digits
int A = 0, B = 0;
for (int pos = 0; pos < 14; ++pos){
int d = last14[pos];
if (pos % 2 == 0){ // A digit
int k = pos/2;
A |= (d << (2*k));
} else { // B digit
int k = pos/2;
B |= (d << (2*k));
}
}
// Clamp to [0, N-1]
if (A >= N) A = N-1;
if (B >= N) B = N-1;
return {A, B};
}
