#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 10005;
static vector<int> adj[MAXN];
static int pu = -1, pv = -1, t[4] = {0,0,0,0}, r[4] = {0,0,0,0}, s = -1, c = -1;
static bool p = false, h = false, e = true;
static vector<int> bfs_from(int src, int N) {
vector<int> dist(N, -1);
if(src < 0 or src >= N) return dist;
queue<int> q;dist[src] = 0;q.push(src);
while(!q.empty()) {
int v = q.front(); q.pop();
for (int to : adj[v]) {
if (to >= 0 and to < N and dist[to] == -1) {
dist[to] = dist[v] + 1;
q.push(to);
}
}
}
return dist;
}
static pair<int,int> recompute_diameter(int N){
int start = 0;
auto d0 = bfs_from(start, N);
bool any = false;
for (int i = 0; i < N; ++i) if (d0[i] != -1) { any = true; break; }
if (!any) return {0,0};
int u = start;
for (int i = 0; i < N; ++i) if (d0[i] > d0[u]) u = i;
auto du = bfs_from(u, N);
int v = u;
for (int i = 0; i < N; ++i) if (du[i] > du[v]) v = i;
return {u, v};
}
int send_message(int N, int i, int Pi){
if(Pi >= 0){
if(i >= 0 and i < N and Pi >= 0 and Pi < N){
adj[i].push_back(Pi);adj[Pi].push_back(i);
}
}
auto pr = recompute_diameter(N);
int u = pr.first, v = pr.second;
if(u != pu or v != pv){
pu = u; pv = v;
t[0] = u % 10;t[1] = (u / 10) % 10;t[2] = v % 10;t[3] = (v / 10) % 10;
int a = 0;
for(int i = 0; i < 4; i++){
a += (t[i] + 3) / 4;
}
int nmsg = 2 * a;
if(nmsg > 24) nmsg = 24;
int sched = N - nmsg;
if (sched <= i) sched = i+1;
s = sched;p = true;h = false;
return 0;
}
if(p and i < s){
return 0;
}
if(p and i >= s and !h){
for(int i = 0; i < 4; i++) r[i] = t[i];
h = true;p = false;e = true;c = -1;
return 0;
}
if(h){
if(e){
int pos = -1;
for(int i = 0; i < 4; i++) if (r[i] > 0){pos = i; break;}
if(pos == -1){
h = false;
return 0;
}
c = pos;e = false;
return (c + 1);
}else{
int pos = c;
if(pos < 0 or pos >= 4){
e = true;
return 0;
}
int step = min(4, r[pos]);
r[pos] -= step;
e = true;
bool tt = false;
for(int i = 0; i < 4; i++) if(r[i] > 0){tt = true; break;}
if(!tt) h = false;
return step;
}
}
return 0;
}
pair<int,int> longest_path(vector<int> S){
int n = S.size();
bool tr = false, used = false;
array<int,4> num = {0,0,0,0};
pair<int,int> ls = {0,0};
bool bl = true;
int ans = -1;
for(int i = 0; i < n; ++i){
int x = S[i];
if(x == 0){
if(tr && used){
int u = num[0] + 10 * num[1];
int v = num[2] + 10 * num[3];
ls = {u, v};
}
tr = true;
bl = true;
ans = -1;
used = false;
num = {0,0,0,0};
continue;
}
if(!tr) continue;
if(x < 1 or x > 4){
bl = true;
ans = -1;
continue;
}
if(bl){
ans = x - 1;
bl = false;
} else {
if(ans >= 0 and ans < 4){
num[ans] += x;
used = true;
}
bl = true;
ans = -1;
}
}
if(tr && used){
int u = num[0] + 10 * num[1];
int v = num[2] + 10 * num[3];
ls = {u, v};
}
return ls;
}
