#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
void dfs(int u, int p, vi &dist, vvi &adj) {
for (auto &v : adj[u]) {
if (v == p) continue;
dist[v] = dist[u] + 1;
dfs(v, u, dist, adj);
}
}
int furthest_from(int u, int n, vvi &adj) {
vector<int> dist(n);
dfs(u, u, dist, adj);
int f = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f]) f = i;
return f;
}
int dist_between(int n, int u, int v, vvi &adj) {
vector<int> dist(n);
dfs(u, u, dist, adj);
return dist[v];
}
pi furthest_pair(int n, vvi &adj) {
vector<int> dist(n);
dfs(0, 0, dist, adj);
int f1 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f1]) f1 = i;
dist = vi(n, 0);
dfs(f1, f1, dist, adj);
int f2 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f2]) f2 = i;
return {min(f1, f2), max(f1, f2)};
}
vi to_base(ll A, ll b, int pad = 0) {
vi ans;
while (A > 0LL) {
ans.push_back(A % b);
A /= b;
}
while (ans.size() < pad) ans.push_back(0);
return ans;
}
ll from_base(vi bx, ll b) {
ll po = 1;
ll ans = 0;
for (auto &el : bx) {
ans += ll(el) * po;
po *= b;
}
return ans;
}
const int CN = 57, CK = 4;
int TOTAL_MASKS = 0;
vector<uint64_t> masks;
unordered_map<uint64_t, int> umap;
void initialise_ranks(int N, int K) {
TOTAL_MASKS = 0;
masks.clear();
uint64_t initial = 0;
auto dfs = [&](const auto &self, uint64_t cur, int idx, int rem) {
if (rem == 0) {
masks.push_back(cur);
umap[cur] = TOTAL_MASKS++;
return;
}
for (int i = idx; i < N; i++) {
uint64_t nxt = cur | (1LL << i);
self(self, nxt, i+1, rem-1);
}
};
dfs(dfs, initial, 0, K);
}
vvi adj;
pi fr;
int diam = 0, cpos = 0;
int U = 0, V = 0, rU = 0, rV = 0;
int uv_comb = 0;
vector<int> change_types;
int x = 0, actual_step = 0;
bool changed = false;
int send_message(int n, int i, int Pi) {
if (i <= 1) {
adj.assign(n+1, vi());
initialise_ranks(CN, CK);
}
x = n - 65;
adj[Pi].push_back(i);
adj[i].push_back(Pi);
if (i < x) return 0;
int step = actual_step++;
if (step == 0) {
fr = furthest_pair(n, adj); diam = dist_between(n, fr.first, fr.second, adj);
U = fr.first; V = fr.second;
rU = U, rV = V;
uv_comb = 10000 * U + V;
}
pi cfr = furthest_pair(n, adj);
int u = cfr.first, v = cfr.second;
int cdiam = dist_between(n, u, v, adj);
int type = cdiam == diam ? 0 : (dist_between(n, i, V, adj) == cdiam ? 1 : 2); // if the diameter changed, did we switch u or v
change_types.push_back(type);
diam = cdiam;
if (type == 1) {
U = i;
} else if (type == 2) {
V = i;
if (step < 14) U = V;
}
int MSB = uv_comb / TOTAL_MASKS;
int LSB = uv_comb % TOTAL_MASKS;
uint64_t mask1 = masks[LSB];
vector<int> uvmask(57, 0);
int ones_seen = 0; for (int i = 0; i < 57; i++) {
if (!(mask1 & (1LL << i))) continue;
vi l4 = to_base(MSB, 4, 4);
uvmask[i] = l4[ones_seen]+1;
ones_seen++;
}
if (step < 57) {
return uvmask[step];
} else if (step < 60) {
if (type == 1) return 4;
int px = 63; for (int k = 0; k < 57; k++) if (change_types[k] == 1) px = k;
vi p4 = to_base(px, 4, 3);
return p4[step - 57];
} else if (step < 63) {
if (type == 2) return 4;
int px = 63; for (int k = 0; k < 60; k++) if (change_types[k] == 2) px = k;
vi p4 = to_base(px, 4, 3);
return p4[step - 60];
} else if (step == 63) {
int px = 5; for (int k = 0; k < 4; k++) if (change_types[60+k] == 1) px = k;
if (px == 5) return 4;
else return px;
} else if (step == 64) {
if (change_types[63] == 2) {
if (type == 0) return 3;
else if (type == 1) return 4;
else return 2; // double overlap
} else {
if (type == 0) return 0;
else if (type == 1) return 1;
else return 2;
}
} else {
return 0; // shouldn't happen
}
}
// 0 - no change, 1 - change u, 2 - change v
pi longest_path(vi S) {
initialise_ranks(CN, CK);
int n = S.size();
int x = n - 65;
vi nonzero; uint64_t mask = 0;
for (ll i = 0; i < 57; i++) {
if (S[x+i] == 0) continue;
nonzero.push_back(S[x+i]-1);
mask |= 1LL << i;
}
int MSB = from_base(nonzero, 4), LSB = umap[mask];
int combined = MSB * TOTAL_MASKS + LSB;
int u = combined / 10'000, v = combined % 10000;
if (S[x+57] == 4 || S[x+58] == 4 || S[x+59] == 4) {
for (int i = 57; i < 60; i++) if (S[x+i] == 4) u = x+i;
} else {
int um = from_base({S[x+57], S[x+58], S[x+59]}, 4);
if (um != 63) u = x + um;
}
if (S[x+60] == 4 || S[x+61] == 4 || S[x+62] == 4) {
for (int i = 60; i < 63; i++) if (S[x+i] == 4) v = x+i;
} else {
int vm = from_base({S[x+60], S[x+61], S[x+62]}, 4);
if (vm != 63) v = x + vm;
}
if (S[x+63] != 4) u = x + 60 + S[x+63];
if (S[x+64] == 0) {}
else if (S[x+64] == 1) u = x + 64;
else if (S[x+64] == 2) v = x + 64;
else if (S[x+64] == 3) v = x + 63;
else if (S[x+64] == 4) {u = x + 64; v = x + 63;}
int A = u, B = v;
return {A, B};
}
