#include "migrations.h"
using namespace std;
#include <bits/stdc++.h>
vector<vector<int>> adj;
vector<int> dist_from_0;
void dfs(int u){
for(int v : adj[u]){
dist_from_0[v] = dist_from_0[u] + 1;
dfs(v);
}
}
int ipow(int base, int exp) {
int result = 1;
while (exp > 0) {
if (exp & 1) result *= base;
base *= base;
exp >>= 1;
}
return result;
}
int furtherest = 0;
int send_message(int N, int i, int Pi) {
if(i == 1){
adj.resize(N);
dist_from_0.resize(N, 0);
adj[Pi].push_back(1);
return 0;
}
adj[Pi].push_back(i);
if(i < 9992) return 0;
if(i == 9992){
int max_dist = 0;
dfs(0);
for(int iz = 0; iz < dist_from_0.size(); iz ++){
if(dist_from_0[iz] > max_dist){
max_dist = dist_from_0[iz];
furtherest = iz;
}
}
return (furtherest / ipow(5, 5)) % 5;
}
if(i == 9993) return (furtherest / ipow(5, 4)) % 5;
if(i == 9994) return (furtherest / ipow(5, 3)) % 5;
if(i == 9995) return (furtherest / ipow(5, 2)) % 5;
if(i == 9996) return (furtherest / ipow(5, 1)) % 5;
//if(i == 9997) return (furtherest) % 5;
if(i < 9998) return furtherest / ipow(5, 9997 - i) % 5;
if(i == 9998){
int max_dist = 0;
int furth = 0;
dfs(0);
for(int iz = 0; iz < dist_from_0.size(); iz ++){
if(dist_from_0[iz] > max_dist){
max_dist = dist_from_0[iz];
furth = iz;
}
}
if(furth == furtherest){
return 0;
}
furtherest = furth;
if(furtherest < 9997){
return furtherest - 9992;
}
}
if(i == 9999){
int max_dist = 0;
int furth = 0;
dfs(0);
for(int iz = 0; iz < dist_from_0.size(); iz ++){
if(dist_from_0[iz] > max_dist){
max_dist = dist_from_0[iz];
furth = iz;
}
}
furtherest = furth;
if(furtherest == 9997){
return 1;
}
if(furtherest == 9998){
return 2;
}
if(furtherest == 9999){
return 3;
}
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
if(S[9998] == 0 && S[9999] == 0){
int res = 0;
res += S[9992] * ipow(5, 5);
res += S[9993] * ipow(5, 4);
res += S[9994] * ipow(5, 3);
res += S[9995] * ipow(5, 2);
res += S[9996] * ipow(5, 1);
res += S[9997] * ipow(5, 0);
return {0, res};
}
if(S[9999] == 0){
return {0, S[9998] + 9992};
}
return {0, S.back() + 9996};
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o migrations grader.cpp migrations.cpp
6
0 0 2 2 3
*/
