#include "migrations.h"
using namespace std;
#include <bits/stdc++.h>
vector<vector<int>> adj;
vector<int> dist_from_0;
void dfs(int u, vector<int>& dist){
for(int v : adj[u]){
dist[v] = dist[u] + 1;
dfs(v, dist);
}
}
int furtherest_node_from(int u){
vector<int> dist(adj.size(), 0);
int max_dist = 0;
int far = 0;
dfs(u, dist);
for(int iz = 0; iz < dist_from_0.size(); iz ++){
if(dist[iz] > max_dist){
max_dist = dist_from_0[iz];
far = iz;
}
}
return far;
}
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 end_1;
int end_2;
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 < 9998) return 0;
if(i == 9998){
end_1 = furtherest_node_from(0);
end_2 = furtherest_node_from(end_1);
return end_1;
}
if(i == 9999){
//
if(Pi == end_1){
return 10000 + end_2; // First end is 9999
}
if(Pi == end_2){
return 20000; // Second end is 9999
}
return end_2;
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
if(S[9999] == 20000){
return {S[9998], 9999};
}
if(S[9999] >= 10000){
return {9999, S[9999] - 10000};
}
return {S[9998], S[9999]};
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o migrations grader.cpp migrations.cpp
6
0 0 2 2 3
*/
