#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
pair<int, int> createTree(int n, int* tree, bool* visited, vector<unordered_map<int, int>> &graph, pair<pair<int, int>, pair<int, int>>* depth, unordered_set<int> &nodes){
visited[n] = true;
nodes.insert(n);
// depth[n].first = {d.first, dist};
for(const pair<int, int> &child : graph[n]){
if(visited[child.first]) continue;
if(child.second == 0) continue;
tree[child.first] = n;
pair<int, int> d = createTree(child.first, tree, visited, graph, depth, nodes);
int dist = d.second + child.second;
// cout << "| " << n << ' ' << child.first << ' ' << dist << '\n';
if(dist > depth[n].first.second){
// cout << "Swapped: " << depth[n].first.first << ' ' << child.first << '\n';
depth[n].second = make_pair(child.first, dist);
swap(depth[n].second, depth[n].first);
}else if(dist > depth[n].second.second){
// cout << "Swapped: " << depth[n].second.first << ' ' << child.first << '\n';
// cout << "??: " << depth[n].second.second << ' ' << dist << '\n';
depth[n].second = make_pair(child.first, dist);
}else{
// cout << "didnt make it :(\n";
}
}
return depth[n].first;
}
void dfsUPUP(int node, bool* visited, int* up, int* upup, int prev, vector<unordered_map<int, int>> &graph){
visited[node] = node;
for(const pair<int, int> &child : graph[node]){
if(visited[child.first]) continue;
if(child.second == 0) continue;
dfsUPUP(child.first, visited, up, upup, max(up[child.first], child.second + prev), graph);
}
upup[node] = prev;
}
pair<int, int> dfsDiagonal(int node, bool* visited, vector<unordered_map<int, int>> &graph){
pair<int,int> mx = {node, 0};
// cout << "| " << node << '\n';
visited[node] = true;
for(const pair<int, int> &child : graph[node]){
if(visited[child.first]) continue;
if(child.second == 0) continue;
pair<int, int> d = dfsDiagonal(child.first, visited, graph);
if(d.second + child.second > mx.second){
mx = {d.first, d.second + child.second};
}
}
// cout << node << ' ' << mx.second << '\n';
return mx;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
bool visited[100005] = {false};
int t = N-M-1;
vector<int> radii(t+1);
vector<int> diameter(t+1);
vector<int> centers(t+1);
vector<unordered_map<int, int>> graph(N);
for(int i = 0; i < M; i++){
graph[A[i]][B[i]] = T[i];
graph[B[i]][A[i]] = T[i];
}
int tree[100005] = {-1};
pair<pair<int, int>, pair<int, int>> depth[100005];
for(int i = 0; i < 100005; i++) depth[i] = {{-1,0}, {-1,0}};
int up[100005] = {0};
bool upupVisited[100005] = {false};
int upup[100005] = {0};
int index = -1;
for(int root = 0; root < N; root++){
if(visited[root]) continue;
// cout << "tree\n";
// cout << "root: " << root << '\n';
unordered_set<int> nodes;
createTree(root, tree, visited, graph, depth, nodes);
index++;
// cout << "depth: ";
// for(const int &node : nodes) cout << node << ":" <<
// depth[node].first.first << ',' << depth[node].first.second
// << "(" << depth[node].second.first << ',' << depth[node].second.second << ' ';
// cout << '\n';
if(nodes.size() == 1){
radii[index] = 0;
diameter[index] = 0;
}
for(const int &node : nodes){
if(tree[node] == -1) continue;
if(depth[tree[node]].first.first == node){
up[node] = depth[tree[node]].second.second + graph[node][tree[node]];
}else{
up[node] = depth[tree[node]].first.second + graph[node][tree[node]];
}
}
// cout << "up: ";
// for(const int &node : nodes) cout << node << ":" << up[node] << ' ';
// cout << '\n';
dfsUPUP(root, upupVisited, up, upup, 0, graph);
int center = root;
int radius = INT_MAX;
int dm = 0;
for(const int &node : nodes){
int dist = max(upup[node], depth[node].first.second);
if(dist < radius){
radius = dist;
center = node;
}
dm = max(dm, dist);
}
centers[index] = center;
radii[index] = radius;
diameter[index] = dm;
}
for(int i = 0; i < t+1; i++){
cout << centers[i] << ' ';
}
cout << '\n';
// for(int i = 0; i < t+1; i++){
// cout << diameter[i] << ' ';
// }
// cout << '\n';
// int mxDist = 0;
// int mxRad = -1;
// int mxRad1 = -1;
// for(int i = 0; i < t+1; i++) mxDist = max(mxDist, diameter[i]);
// for(int i = 1; i < t+1; i++) {
// mxDist = max(mxDist, radii[0] + L + radii[i]);
// if(radii[i] > mxRad){
// mxRad1 = radii[i];
// swap(mxRad1, mxRad);
// }else if(radii[i] > mxRad1) mxRad1 = radii[i];
// }
// if(t+1 >= 3){
// mxDist = max(mxDist, mxRad1 + mxRad + L * 2);
// }
// cout << graph.size();
for(int i = 1; i < t+1; i++) {
// cout << centers[i] << ' ' << centers[0] << '\n';
graph[centers[0]][centers[i]] = L;
graph[centers[i]][centers[0]] = L;
}
// cout << "pop" << endl;
bool visited1[100005] = {false};
bool visited2[100005] = {false};
pair<int, int> d1 = dfsDiagonal(0, visited1, graph);
// cout << "poop\n";
pair<int, int> d2 = dfsDiagonal(d1.first, visited2, graph);
// cout << d1.first << ' ' << d2.first << '\n';
return d2.second;
}
// int A[] = {0, 8, 2, 5, 5, 1, 1, 10};
// int B[] = {8, 2, 7, 11, 1, 3, 9, 6};
// int T[] = {4, 2, 4, 3, 7, 1, 5, 3};
// int main(){
// int ans = travelTime(12, 8, 2, A, B, T);
// cout << ans << '\n';
// return 0;
// }
