#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <math.h>
#include <random>
#include <string>
#include <cstring>
#include "dreaming.h"
#include <set>
#include <vector>
#include <map>
using namespace std;
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
const int inf = 2e9;
const int N = 2e5 + 15;
int n, m, l, maxdiam, sz[N], d[N], center[N], deg[N], p[N], par[N];
vector <pii> g[N];
set <int> c, comp;
vector <int> f[N];
bool used[N];
queue <int> q;
int find(int v) {
if(v == p[v])
return v;
return p[v] = find(p[v]);
}
void unio(int a, int b) {
a = find(a);
b = find(b);
if(a != b) {
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
}
void dfs(int v, int p = -1) {
par[v] = p;
for(pii to : g[v]) {
if(to.f != p) {
d[to.f] = d[v] + to.se;
dfs(to.f, v);
}
}
}
void bfs(int componen) {
vector <int> path = {};
used[componen] = true;
for(int i : f[componen])
d[i] = 0;
dfs(f[componen].back());
int ind = -1;
for(int i : f[componen])
if(ind == -1 || d[i] > d[ind])
ind = i;
for(int i : f[componen])
d[i] = 0;
dfs(ind);
int v = ind;
ind = -1;
for(int i : f[componen])
if(ind == -1 || d[i] > d[ind])
ind = i;
for(; ind != v; ind = par[ind])
path.pb(ind);
path.pb(v);
center[componen] = path[path.size() / 2];
for(int i : f[componen])
d[i] = 0;
dfs(center[componen]);
for(int i : f[componen])
d[center[componen]] = max(d[center[componen]], d[i]);
c.insert(center[componen]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, l = L;
for(int i = 0; i < n; ++i)
p[i] = i, sz[i] = 1;
for(int i = 0; i < m; ++i) {
g[A[i]].pb(mp(B[i], T[i]));
g[B[i]].pb(mp(A[i], T[i]));
deg[A[i]]++, deg[B[i]]++;
unio(A[i], B[i]);
}
for(int i = 0; i < n; ++i) {
comp.insert(find(i));
f[find(i)].pb(i);
}
for(int i : comp)
if(!used[i])
bfs(i);
for(int i : c)
if(d[i] > d[maxdiam])
maxdiam = i;
for(int i : comp) {
if(find(maxdiam) == i)
continue;
g[maxdiam].pb(mp(center[i], l));
g[center[i]].pb(mp(maxdiam, l));
}
memset(d, 0, sizeof(d));
dfs(0);
int ind = -1;
for(int i = 0; i < n; ++i)
if(ind == -1 || d[i] > d[ind])
ind = i;
memset(d, 0, sizeof(d));
dfs(ind);
return *max_element(d, d + n);
}
