#include "bits/stdc++.h"
#include "dreaming.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
vector<vector<pair<int, int>>> adj;
vector<int> path1, path2;
vector<int> cnt1, cnt2;
void dfs1(vector<bool> &visited, int u)
{
if(visited[u])
return;
visited[u] = true;
for(auto v: adj[u])
{
dfs1(visited, v.fi);
}
}
pair<int, int> extract_components(int N)
{
vector<int> temp;
vector<bool> visited(N, false);
for(int i = 0; i<N; i++)
{
if(!visited[i])
{
dfs1(visited, i);
temp.pb(i);
}
}
pair<int, int> res = mp(0, 0);
temp[0], res.se = temp[1];
return res;
}
void depth(vector<bool> &visited, vector<int> &cnt, int u)
{
visited[u] = true;
for(auto v: adj[u])
{
if(!visited[v.fi])
{
cnt[v.fi] = cnt[u] + v.se;
depth(visited, cnt, v.fi);
}
}
}
pair<int, int> diameter(int N, int u)
{
int a = u, b = u, c = u;
int maxi = 0;
vector<bool> visited(N, false);
vector<int> cnt(N, 0);
depth(visited, cnt, a);
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
b = i;
}
}
cnt.assign(N, 0);
visited.assign(N, false);
depth(visited, cnt, b);
maxi = 0;
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
c = i;
}
}
return mp(b, c);
}
vector<int> bfs(int N, pair<int, int> d)
{
int st = d.fi, en = d.se;
if(st==en)
{
vector<int> temp;
temp.pb(st);
return temp;
}
vector<bool> visited(N, false);
vector<int> parent(N, -1);
queue<int> q;
q.push(st);
visited[st] = true;
bool flag = true;
while(!q.empty()&&flag)
{
int u = q.front();
q.pop();
for(auto v: adj[u])
{
if(visited[v.fi])
continue;
visited[v.fi] = true;
parent[v.fi] = u;
q.push(v.fi);
if(v.fi==en)
flag = false;
}
}
vector<int> path;
while(parent[en]!=-1)
{
path.pb(en);
en = parent[en];
}
path.pb(st);
reverse(path.begin(), path.end());
return path;
}
int solve(int N)
{
int a = 0, b = 0;
int maxi = 0;
vector<bool> visited(N, false);
vector<int> cnt(N, 0);
depth(visited, cnt, a);
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
b = i;
}
}
cnt.assign(N, 0);
visited.assign(N, false);
depth(visited, cnt, b);
maxi = 0;
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
}
}
return maxi;
}
vector<pair<int, int>> emp(0);
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
adj.assign(N, emp);
for(int i = 0; i<M; i++)
{
adj[A[i]].pb(mp(B[i], T[i]));
adj[B[i]].pb(mp(A[i], T[i]));
}
pair<int, int> comps = extract_components(N);
int a = comps.fi, b = comps.se;
pair<int, int> d1 = diameter(N, a);
pair<int, int> d2 = diameter(N, b);
path1 = bfs(N, d1);
path2 = bfs(N, d2);
int len1 = int(path1.size());
int len2 = int(path2.size());
vector<bool> visited(N, false);
cnt1.assign(N, 0);
cnt2.assign(N, 0);
depth(visited, cnt1, path1[0]);
depth(visited, cnt2, path2[0]);
int n1 = path1[0], n2 = path2[0];
int dif = 1e8;
for(int i = 1; i<len1; i++)
{
if(abs(cnt1[path1[i]]-(cnt1[path1[len1-1]]-cnt1[path1[i]]))<dif)
{
dif = abs(cnt1[path1[i]]-(cnt1[path1[len1-1]]-cnt1[path1[i]]));
n1 = path1[i];
}
}
dif = 1e8;
for(int i = 1; i<len2; i++)
{
if(abs(cnt2[path2[i]]-(cnt2[path2[len2-1]]-cnt2[path2[i]]))<dif)
{
dif = abs(cnt2[path2[i]]-(cnt2[path2[len2-1]]-cnt2[path2[i]]));
n2 = path2[i];
}
}
path1.clear();
path2.clear();
cnt1.clear();
cnt2.clear();
adj[n1].pb(mp(n2, L));
adj[n2].pb(mp(n1, L));
int res = solve(N);
return res;
}
