/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
typedef long long ll;
const int INF = INT_MAX / 2;
struct Edge
{
int u, v;
int w;
int other (int x)
{
return (u ^ v ^ x);
}
bool primary;
};
int N, M;
vector <Edge> edges;
vector <vector <Edge*>> adj;
vector <int> special;
vector <int> cost;
vector <int> parent;
vector <int> parw;
vector <int> depth;
int BITS;
vector <vector <int>> anc;
vector <vector <int>> ancw;
int ancestor (int &u, int k)
{
int maxw = 0;
for(int bit = BITS - 1; bit >= 0; bit--)
if((k >> bit) & 1)
{
maxw = max(maxw, ancw[u][bit]);
u = anc[u][bit];
}
return maxw;
}
int dist (int u, int v)
{
int maxw = 0;
if(depth[u] > depth[v])
maxw = max(maxw, ancestor(u, depth[u] - depth[v]));
if(depth[v] > depth[u])
maxw = max(maxw, ancestor(v, depth[v] - depth[u]));
if(u == v)
return maxw;
for(int bit = BITS - 1; bit >= 0; bit--)
if(anc[u][bit] != anc[v][bit])
{
maxw = max(maxw, ancw[u][bit]);
maxw = max(maxw, ancw[v][bit]);
u = anc[u][bit];
v = anc[v][bit];
}
maxw = max(maxw, parw[u]);
maxw = max(maxw, parw[v]);
return maxw;
}
void init (int _N, int _M, vector <int> U, vector <int> V, vector <int> W)
{
N = _N;
M = _M;
/// Process edges
edges = vector <Edge> (M);
for(int i = 0; i < M; i++)
edges[i] = Edge{U[i], V[i], W[i], false};
adj = vector <vector <Edge*>> (N);
for(int i = 0; i < M; i++)
{
adj[edges[i].u].push_back(&edges[i]);
adj[edges[i].v].push_back(&edges[i]);
}
/// Use DSU to find minimum spanning tree
{
vector <int> par (N);
for(int u = 0; u < N; u++)
par[u] = u;
function <int (int)> findRoot = [&] (int u)
{
if(par[u] == u)
return u;
return par[u] = findRoot(par[u]);
};
function <bool (int, int)> join = [&] (int u, int v)
{
u = findRoot(u);
v = findRoot(v);
if(u == v)
return false;
par[u] = v;
return true;
};
// Sort edges by weight
vector <int> edgeOrder (M);
for(int i = 0; i < M; i++)
edgeOrder[i] = i;
sort(edgeOrder.begin(), edgeOrder.end(),
[&] (const int &x, const int &y)
{
return edges[x].w < edges[y].w;
});
// Find "primary" edges that form the spanning tree
for(int j = 0; j < M; j++)
{
int i = edgeOrder[j];
if(join(edges[i].u, edges[i].v) == true)
edges[i].primary = true;
}
}
/// Use DFS to find the structure of the tree
parent = vector <int> (N, -1);
parw = vector <int> (N, 0);
depth = vector <int> (N, 0);
vector <bool> visited (N, false);
function <void (int)> dfs = [&] (int u)
{
visited[u] = true;
for(Edge* e : adj[u])
if(e->primary == true)
{
int v = e->other(u);
if(visited[v] == false)
{
depth[v] = depth[u] + 1;
parent[v] = u;
parw[v] = e->w;
dfs(v);
}
}
};
for(int u = 0; u < N; u++)
if(visited[u] == false)
dfs(u);
/// Use binary lifting to get ancestors and be able to compute distance
BITS = 0;
while((1 << BITS) <= N)
BITS++;
anc = vector <vector <int>> (N, vector <int> (BITS, -1));
ancw = vector <vector <int>> (N, vector <int> (BITS, 0));
for(int u = 0; u < N; u++)
{
anc[u][0] = parent[u];
ancw[u][0] = parw[u];
}
for(int bit = 1; bit < BITS; bit++)
for(int u = 0; u < N; u++)
{
if(anc[u][bit - 1] != -1)
{
anc[u][bit] = anc[anc[u][bit - 1]][bit - 1];
ancw[u][bit] = max(ancw[u][bit - 1], ancw[anc[u][bit - 1]][bit - 1]);
}
}
/// Find special cost for each node
// Intersection nodes
special = vector <int> (N, INF);
for(int u = 0; u < N; u++)
if((int) adj[u].size() >= 3)
{
vector <int> aux;
for(Edge* e : adj[u])
aux.push_back(e->w);
sort(aux.begin(), aux.end());
special[u] = aux[2];
}
// Cycle nodes
for(int i = 0; i < M; i++)
if(edges[i].primary == false)
special[edges[i].u] = min(special[edges[i].u], edges[i].w);
/// Use DSU to find additional cost for each node
{
vector <int> par (N);
for(int u = 0; u < N; u++)
par[u] = u;
vector <int> wpar (N, INF);
vector <int> dim (N, 1);
vector <int> minCost (N, INF);
function <int (int)> findRoot = [&] (int u)
{
if(par[u] == u)
return u;
return findRoot(par[u]);
};
function <void (int, int, int)> join = [&] (int u, int v, int w)
{
u = findRoot(u);
v = findRoot(v);
if(u == v)
return;
if(dim[u] > dim[v])
swap(u, v);
par[u] = v;
wpar[u] = w;
dim[v] += dim[u];
if(minCost[v] == INF && minCost[u] != INF)
minCost[v] = w;
};
vector <int> edgeOrder (M);
for(int i = 0; i < M; i++)
edgeOrder[i] = i;
sort(edgeOrder.begin(), edgeOrder.end(),
[&] (const int &x, const int &y)
{
return edges[x].w < edges[y].w;
});
vector <int> specialOrder (N);
for(int u = 0; u < N; u++)
specialOrder[u] = u;
sort(specialOrder.begin(), specialOrder.end(),
[&] (const int &u, const int &v)
{
return special[u] < special[v];
});
int currEdge = 0;
int currSpecial = 0;
while(currEdge < M || currSpecial < N)
{
if(currSpecial == N || (currEdge < M
&& edges[edgeOrder[currEdge]].w
< special[specialOrder[currSpecial]]))
{
int i = edgeOrder[currEdge];
join(edges[i].u, edges[i].v, edges[i].w);
currEdge++;
}
else
{
int u = specialOrder[currSpecial];
int r = findRoot(u);
if(minCost[r] == INF)
minCost[r] = special[u];
currSpecial++;
}
}
cost = vector <int> (N);
for(int u = 0; u < N; u++)
{
cost[u] = minCost[u];
int v = u;
int maxw = 0;
while(par[v] != v)
{
maxw = max(maxw, wpar[v]);
v = par[v];
cost[u] = min(cost[u], max(maxw, minCost[v]));
}
}
}
}
int getMinimumFuelCapacity (int U, int V)
{
int answer = max(dist(U, V), cost[U]);
if(answer == INF)
return -1;
return answer;
}
