#include "swap.h"
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5+10;
const int lgmx = 18;
const int inf = 1e9+69;
struct edge
{
int x, y, z;
inline bool operator<(const edge& o) const
{
return z < o.z;
}
} edgs[maxn];
int N, M;
vector<int> comp[maxn];
int root[maxn];
bool ispath[maxn];
int fnp[maxn];
pii sars[maxn];
int epar[maxn];
int dpar[maxn];
vector<int> kids[maxn];
inline void invldp(int r, int z)
{
if(!ispath[r]) return;
for(int u: comp[r])
{
//if(!ispath[u])
// cerr << "fuck" << endl;
ispath[u] = false;
fnp[u] = z;
}
}
inline bool isin(int x, pii p)
{
return x == p.first or x == p.second;
}
inline void mrg(int x, int y, int z)
{
if(comp[root[x]].size() < comp[root[y]].size())
swap(x, y);
int rx = root[x];
int ry = root[y];
if(rx == ry)
{
invldp(rx, z);
}
else
{
if( ispath[rx] and ispath[ry] and isin(x, sars[rx]) and isin(y, sars[ry]) )
{
int a = sars[rx].first^sars[rx].second ^ x;
int b = sars[ry].first^sars[ry].second ^ y;
sars[rx] = pii(a, b);
}
else
{
invldp(rx, z);
invldp(ry, z);
}
epar[ry] = z;
dpar[ry] = rx;
for(int u: comp[ry])
{
root[u] = rx;
comp[rx].push_back(u);
}
comp[ry].clear();
}
}
int tin[maxn];
int tout[maxn];
int timer = 0;
void dfs(int v)
{
tin[v] = timer++;
for(int u: kids[v])
dfs(u);
tout[v] = timer;
}
inline bool isanc(int x, int y)
{
return (tin[x] <= tin[y] and tout[y] <= tout[x]);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
::N = N;
::M = M;
for(int i = 0; i < N; i++)
{
root[i] = i;
comp[i].push_back(i);
ispath[i] = true;
fnp[i] = inf;
sars[i] = pii(i, i);
dpar[i] = i;
}
for(int i = 0; i < M; i++)
edgs[i] = {V[i], U[i], W[i]};
sort(edgs, edgs+M);
for(int i = 0; i < M; i++)
{
int x = edgs[i].x;
int y = edgs[i].y;
int z = edgs[i].z;
mrg(x, y, z);
}
int r = 0;
for(int i = 0; i < N; i++)
{
if(dpar[i] != i)
kids[dpar[i]].push_back(i);
else
r = i;
}
//cerr << r << endl;
dfs(r);
}
int getMinimumFuelCapacity(int x, int y)
{
int ans = max(fnp[x], fnp[y]);
int v = x;
int t = 0;
while(!isanc(v, y))
{
ans = max(ans, epar[v]);
v = dpar[v];
t++;
}
assert(t <= lgmx);
t = 0;
v = y;
while(!isanc(v, x))
{
ans = max(ans, epar[v]);
v = dpar[v];
t++;
}
//cerr << t << endl;
assert(t <= lgmx);
if(ans == inf)
return -1;
return ans;
}
