#include "migrations.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ari2 = array<int, 2>; using ari3 = array<int, 3>; using arl2 = array<ll, 2>; using arl3 = array<ll, 3>; template <class T> using vt = vector<T>; #define all(x) begin(x), end(x) #define size(x) (int((x).size())) #define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d)) #define FOR(a,b,c) REP(a,b,c,1) #define ROF(a,b,c) REP(a,b,c,-1) constexpr int mxN = 10005; vt<int> adj[mxN]; int U, V = 1, best = 1, UU, VV = 1; int find_dist(const int i, const int p, const int target, const int d) { if (i == target) return d; int ret = 0; for (const auto &j : adj[i]) if (j != p) ret = max(ret, find_dist(j, i, target, d + 1)); return ret; } int send_message(const int N, const int i, const int Pi) { adj[Pi].push_back(i); adj[i].push_back(Pi); const int iu = find_dist(i, -1, U, 0); const int iv = find_dist(i, -1, V, 0); if (i < N - 28) { if (max(iu, iv) > best) { best = max(iu, iv); if (iv > iu) UU = U = V; VV = V = i; } return 0; } int ret = (i < N - 14 ? UU : VV) >> i - N + (i < N - 14 ? 28 : 14) & 1; if (max(iu, iv) <= best) ret |= 4; else { best = max(iu, iv); if (iv > iu) U = V; else ret |= 2; V = i; } return ret; } pair<int, int> longest_path(const vt<int> S) { const int N = size(S); U = 0, V = 0; FOR(i, N - 28, N - 15) U |= (S[i] & 1) << i - N + 28; FOR(i, N - 14, N - 1) V |= (S[i] & 1) << i - N + 14; FOR(i, N - 28, N - 1) { if (S[i] & 4) continue; if (~S[i] & 2) U = V; V = i; } return {U, V}; }