#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
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(int A, int b, int pad = 0) {
vi ans;
while (A > 0) {
ans.push_back(A % b);
A /= b;
}
while (ans.size() < pad) ans.push_back(0);
return ans;
}
int from_base(vi bx, int b) {
int po = 1;
int ans = 0;
for (auto &el : bx) {
ans += el * po;
po *= b;
}
return ans;
}
vector<bool> bsearch(int x) { // record decision log of binary search to find x
vector<bool> log;
int lo = 0, hi = 10000;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid < x) {
log.push_back(true);
lo = mid + 1;
} else {
hi = mid;
log.push_back(false);
}
}
return log;
}
vvi adj;
pi fr;
int diam = 0;
int prev_change = 0;
int x = 0;
int send_message(int n, int i, int Pi) {
if (i <= 1) adj.assign(n+1, vi());
x = n - 28;
adj[Pi].push_back(i);
adj[i].push_back(Pi);
if (i < x) return 0;
int step = i - x;
if (step == 0) {fr = furthest_pair(n, adj); diam = dist_between(n, fr.first, fr.second, adj); prev_change = fr.second;}
int ans = 0;
if (step < 14) ans = min(1, fr.first & (1 << step));
else ans = min(1, fr.second & (1 << (step - 14)));
pi cfr = furthest_pair(n, adj);
int u = cfr.first, v = cfr.second;
int cdiam = dist_between(n, u, v, adj);
if (cdiam == diam) {
return ans;
} else if (dist_between(n, i, prev_change, adj) == cdiam) {
diam = cdiam;
prev_change = i;
return ans + 2;
} else {
prev_change = i;
diam = cdiam;
return ans + 4;
}
return ans;
}
pi longest_path(vi S) {
int n = S.size();
int x = n - 28;
int u = 0, v = 0;
vector<pi> switches;
for (int i = x; i < x + 14; i++) {
if (S[i] >= 4) {
switches.push_back({i, 0});
u |= (S[i] - 4) << (i - x);
} else if (S[i] >= 2) {
switches.push_back({i, 1});
u |= (S[i] - 2) << (i - x);
} else {
u |= S[i] << (i - x);
}
}
for (int i = x + 14; i < n; i++) {
if (S[i] >= 4) {
switches.push_back({i, 0});
v |= (S[i] - 4) << (i - x - 14);
} else if (S[i] >= 2) {
switches.push_back({i, 1});
v |= (S[i] - 2) << (i - x - 14);
} else {
v |= S[i] << (i - x - 14);
}
}
int A = u, B = v;
int L = v;
for (auto &el : switches) {
int w = el.first;
if (el.second) {
(L == A ? B : A) = w;
} else {
(L == A ? A : B) = w;
}
L = w;
}
return {A, B};
}
