#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
namespace self {
int N = -1;
vector<int> P = { 0 }, D = { 0 };
vector<vector<int>> adjlist = { {} };
int bestD = 0, bestI = 0, changeddiffS = 15, changeddiffE = 15;
bool changed = false;
pair<int, int> bestes = { 0, 0 };
pair<int, int> mem;
}
using namespace self;
int findE(int S, int E1, int E2, int E3) {
queue<int> bfs;
vector<bool> visited(N, false);
vector<int> d(N, -1);
bfs.push(S);
d[S] = 0;
visited[S] = true;
while (!bfs.empty()) {
int i = bfs.front();
bfs.pop();
for (int j : adjlist[i]) {
if (visited[j]) continue;
visited[j] = true;
d[j] = d[i] + 1;
bfs.push(j);
}
}
int maxd = *max_element(d.begin(), d.end());
vector<int> candidates;
for (int x : {E1, E2, E3}) if (d[x] == maxd) candidates.push_back(x);
if (!candidates.empty()) return candidates[rand() % candidates.size()];
vector<int> all;
for (int i = 0; i < N; i++) if (d[i] == maxd) all.push_back(i);
return all[rand() % all.size()];
}
int send_message(int _N, int _i, int Pi) {
if (N == -1) {
N = _N;
srand(1434);
}
changed = false;
P.push_back(Pi);
adjlist[Pi].push_back(_i);
adjlist.push_back({ Pi });
D.push_back(D[Pi] + 1);
if (bestD < D[_i]) {
bestI = _i;
bestD = D[_i];
}
if (N - _i <= 15) {
int S = bestI, E;
if (S == _i) E = findE(S, bestes.first, bestes.second, bestes.second);
else E = findE(S, _i, bestes.first, bestes.second);
//)cout << S << ' ' << E << '\n';
if (S > E) swap(S, E);
if (N <= 15) {
int res = 0;
if (S == bestes.first && E == bestes.second) res = 0;
else if ((S == _i && E == bestes.first) || (E == _i && S == bestes.first)) res = 2;
else res = 1;
if (res == 1) bestes.first = _i;
else if (res == 2) bestes.second = _i;
return res;
}
if ((N - _i == 15 || N - _i == 7 || N - _i <= 5) && !(S == bestes.first && E == bestes.second) ){
if (S != bestes.first && E != bestes.first)
changeddiffS = N - _i;
if (S != bestes.second && E != bestes.second)
changeddiffE = N - _i;
if (S == bestes.first || E == bestes.second) bestes = { S, E };
else bestes = { E, S };
}
if (N - _i > 3) {
int digit = (N - _i - 4) / 2;
if ((N - _i) % 2) {
int S = bestes.first;
if (changeddiffS == 7) S -= (N - 14);
if (changeddiffS == 5) S -= (N - 6);
for (int i = 0; i < digit; i++, S /= 5);
return S % 5;
}
else {
int E = bestes.second;
if (changeddiffE == 7) E -= (N - 14);
if (changeddiffE <= 5) E -= (N - 6);
for (int i = 0; i < digit; i++, E /= 5);
return E % 5;
}
}
if (N - _i == 3) {
if (changeddiffS == 15) return 0;
if (changeddiffS == 7) return 1;
return 7 - changeddiffS;
}
if (N - _i == 2) {
if (changeddiffE == 15) return 0;
if (changeddiffE == 7) return 1;
if (changeddiffE == 5) return 2;
return 6 - changeddiffE;
}
if (changeddiffE >= 2 && changeddiffS > 2) return 0;
if (changeddiffE >= 2 && changeddiffS == 2) return 1;
if (changeddiffE >= 2 && changeddiffS == 1) return 2;
if (changeddiffE == 1 && changeddiffS > 2) return 3;
if (changeddiffE == 1 && changeddiffS == 2) return 4;
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size(), cnt = 0;
if (N <= 15) {
pair<int, int> crntans = { 0, 0 };
for (int i : S) {
if (i == 1) crntans.first = cnt;
if (i == 2) crntans.second = cnt;
cnt++;
}
return crntans;
}
pair<int, int> crntans = { 0, 0 };
if (S[N - 3] == 0) {
for (int j = 0; j < 6; j++) {
crntans.first *= 5;
crntans.first += S[N - 15 + j * 2];
}
}
else if (S[N - 3] == 1) {
crntans.first = N - 14 + S[N - 7] * 5 + S[N - 5];
}
else if (S[N - 3] == 2) {
crntans.first = N - 6 + S[N - 5];
}
else if (S[N - 3] == 3) {
crntans.first = N - 4;
}
else crntans.first = N - 3;
if (S[N - 2] == 0) {
for (int j = 0; j < 6; j++) {
crntans.second *= 5;
crntans.second += S[N - 14 + j * 2];
}
}
else if (S[N - 2] == 1) {
crntans.second = N - 14 + S[N - 6] * 5 + S[N - 4];
}
else if (S[N - 2] == 2) {
crntans.second = N - 6 + S[N - 4];
}
else if (S[N - 2] == 3) {
crntans.second = N - 3;
}
else crntans.second = N - 2;
if (S[N - 1] == 0)
return crntans;
if (S[N - 1] == 1)
return { crntans.second, N - 2 };
if (S[N - 1] == 2)
return { crntans.second, N - 1 };
if (S[N - 1] == 3)
return { N - 1, crntans.first };
return { N - 1, N - 2 };
}
