#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;
//vector<int> ends;
set<int> seen;
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 < 9997) return 0;
if(i == 9997){
end_1 = furtherest_node_from(0);
end_2 = furtherest_node_from(end_1);
if(end_1 > end_2){
int temp = end_1;
end_1 = end_2;
end_2 = temp;
}
seen.insert(end_1);
seen.insert(end_2);
//ends = {end_1, end_2};
//sort(ends.begin(), ends.end());
return end_1;
}
if(i == 9998){
//
return end_2;
}
if(i == 9999){
int new_end1 = furtherest_node_from(0);
int new_end2 = furtherest_node_from(new_end1);
vector<int> new_ends;
new_ends = {new_end1, new_end2};
sort(new_ends.begin(), new_ends.end());
int res = 0;
if(seen.count(new_ends[0]) && seen.count(new_ends[1])){
return 0; // boring case
}
if(new_ends[0] == 9998 && new_ends[1] == 9999){
return 20000;
} // both replaced
if(new_ends[0] < 9998 && new_ends[1] > 9997){
res = new_ends[0];
if(new_ends[1] == 9999) res += 10000;
return res;
}
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
if(S.back() == 0){
return {S[9997], S[9998]};
}
if(S.back() == 1){
return {9998, 9999};
}
if(S.back() < 10000){
return {S.back(), 9998};
} else {
return {S.back()-10000, 9998};
}
return {0, 0};
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o migrations grader.cpp migrations.cpp
6
0 0 2 2 3
*/
