#include "dreaming.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
int n,m,l;
vector<int> u,v,w;
vector<vector<pii>> g,dg;
vector<int> col;
int color;
vector<vector<int>> comp;
vector<int> pnk;
vector<int> dnk;
vector<int> kzpnk;
vector<int> kzdnk;
vector<int> diamp;
vector<int> diamk;
vector<int> diamd;
vector<bool> nadiam;
vector<int> koren;
vector<int> iddist;
int nvkomp;
///prvo za svaku komponentu odredjujemo sta nam treba
///imamo niz col, koji odrzava koji cvor je u kojoj komponenti
/// za to nam treba i graf, gde imamo vector vector parova
/// pustimo dfs za odredjivanje komponenti, klasicno
///za svaku komponentu treba da odredimo dijametar (od kog do kog cvora) i njegovu duzinu
///to radimo dpom, za svaki cvor cuvamo prvi i drugi najduzi krak, njihovu duzinu i list do kog idu
/// sada treba da odredimo sve cvorove koji pripadaju dijametru
///to uradimo tako sto pustimo dfs iz nekog cvora, oznacimo drugi kraj sa true, i ako je neki cvor dete true onda je i njegov roditelj
/// onda pravimo drugi graf, tako sto iz pocetnog uklanjamo sve cvorove koji nisu u dijametru
/// zatim za svaku komponentu pocnemo iz jednog lista i idemo putem, pritom odredjujuci razdaljinu do jednog i drugog kraja
/// cuvajuci pritom idealnu najvecu distancu i cvor odakle je ona
/// zatim odredimo komponentu koja ima najveci najduzi krak
///nju proglasavamo za centralnu
///ans na pocetku postavimo na najveci dijametar
///zatim proverimo za zbir najduzeg kraka centralne komp i l i najduzeg kraka svake druge komp
///zatim odredimo od ostalih (bez centralne) kom dve najvece (sa najduzim krakom) i dodamo dva l
///vratimo odgovor
void dfs(int c){
if(col[c]!=-1)return;
col[c]=color;
for(auto a:g[c]){
if(col[a.fi]!=-1)continue;
dfs(a.fi);//cout<<c<<' ';
}
}
void dp(int c, int p){
kzpnk[c]=c;
kzdnk[c]=c;
for(auto a:g[c]){
if(a.fi==p)continue;
dp(a.fi,c);
if(a.se+pnk[a.fi]>=pnk[c]){
dnk[c]=pnk[c];
kzdnk[c]=kzdnk[c];
pnk[c]=pnk[a.fi]+a.se;
kzpnk[c]=kzpnk[a.fi];
}
else if(a.se+pnk[a.fi]>=dnk[c]){
dnk[c]=a.se+pnk[a.fi];
kzdnk[c]=kzpnk[a.fi];
}
}
}
void popuni(int c, int p){
if(nadiam[c])return;
for(auto a:g[c]){
if(a.fi==p)continue;
popuni(a.fi,c);
if(nadiam[a.fi])nadiam[c]=true;
}
}
int travelTime(int N, int M, int L, int U[], int V[], int W[]) {
n=N;m=M;l=L;
v.resize(m);
u.resize(m);
w.resize(m);
for(int i=0;i<m;i++){
v[i]=V[i];
u[i]=U[i];
w[i]=W[i];
}
g.resize(n);
color=0;
for(int i=0;i<n;i++)g[i].clear();
for(int i=0;i<m;i++){
g[v[i]].pb(mp(u[i],w[i]));
g[u[i]].pb(mp(v[i],w[i]));
}
//for(int i=0;i<n;i++){
// cout<<i<<": ";
// for(auto a:g[i])cout<<a.fi<<' ';
// cout<<endl;
//}
col.assign(n,-1);
for(int i=0;i<n;i++){
if(col[i]!=-1)continue;
dfs(i);
color++;
}
//for(int i=0;i<n;i++)cout<<col[i]<<' ';
//cout<<endl;
comp.resize(color);
for(int i=0;i<color;i++){
comp[i].clear();
}
for(int i=0;i<n;i++)comp[col[i]].pb(i);
pnk.assign(n,0);
dnk.assign(n,0);
kzpnk.assign(n,-1);
kzdnk.assign(n,-1);
diamd.assign(color,-1);
diamk.assign(color,-1);
diamp.assign(color,-1);
for(int i=0;i<color;i++){
dp(comp[i][0],-1);
for(auto a:comp[i]){
if(pnk[a]+dnk[a]>diamd[i]){
diamd[i]=pnk[a]+dnk[a];
diamp[i]=kzpnk[a];
diamk[i]=kzdnk[a];
}
}
}
//for(int i=0;i<n;i++)cout<<kzpnk[i]<<' '<<kzdnk[i]<<endl;
//cout<<"aaaa"<<endl;
//for(int i=0;i<color;i++)cout<<diamp[i]<<' '<<diamk[i]<<' '<<diamd[i]<<endl;
//cout<<"dobro je"<<endl;
nadiam.assign(n,false);
for(int i=0;i<color;i++){
nadiam[diamk[i]]=true;
popuni(diamp[i],-1);
}
dg.resize(n);
for(int i=0;i<n;i++)dg[i].clear();
for(int i=0;i<n;i++){
for(auto a:g[i]){
if(nadiam[a.fi])dg[i].pb(a);
}
}
koren.assign(color,-1);
iddist.assign(color,0);
for(int i=0;i<color;i++){
iddist[i]=diamd[i];
koren[i]=diamp[i];
int tren=diamp[i];
int prev=-1;
int d1=diamd[i];
int d2=0;
if(comp[i].size()<=2)continue;
while(tren!=diamk[i]){
int raz;
int tmp=tren;
tie(tren,raz)=dg[tmp][0];
if(tren==prev)tie(tren,raz)=dg[tmp][1];
prev=tmp;
d2+=raz;
d1-=raz;
if(max(d1,d2)<iddist[i]){
iddist[i]=max(d1,d2);
koren[i]=tren;
}
}
}
nvkomp=0;
for(int i=0;i<color;i++){
if(iddist[i]>iddist[nvkomp])nvkomp=i;
}
int ans=0;
for(int i=0;i<color;i++)ans=max(ans,diamd[i]);
for(int i=0;i<color;i++){
if(i==nvkomp)continue;
ans=max(ans,l+iddist[nvkomp]+iddist[i]);
}
if(color<=2)return ans;
int dnvkomp=0;
if(nvkomp==0)dnvkomp++;
for(int i=0;i<color;i++){
if(i==nvkomp)continue;
if(iddist[dnvkomp]<iddist[i])dnvkomp=i;
}
for(int i=0;i<color;i++){
if(i==nvkomp)continue;
if(i==dnvkomp)continue;
ans=max(ans,iddist[dnvkomp]+iddist[i]+l+l);
}
return ans;
}
