#include "swap.h"
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef vector < int > vi;
typedef pair < int, int > pii;
const int N = 2e5 + 500;
const int INF = 0x3f3f3f3f;
const int LOG = 18;
int par[N], kad[N], postao[N], siz[N], deg[N];
vector < pair < int, pii > > edg;
int pr(int x, int tren){
if(par[x] == x || kad[x] > tren)
return x;
return pr(par[x], tren);
}
void mrg(int x, int y, int z){
if(pr(x, z) == pr(y, z)){
x = pr(x, z);
postao[x] = min(postao[x], z);
return;
}
deg[x]++; deg[y]++;
bool dobar = (deg[x] >= 3 || deg[y] >= 3);
x = pr(x, z), y = pr(y, z);
if(siz[x] < siz[y])
{x ^= y, y ^= x, x ^= y;}
par[y] = x; kad[y] = z;
siz[x] += siz[y];
postao[x] = min(postao[x], max(postao[y], z));
if(dobar)
postao[x] = min(postao[x], z);
}
void init(int n, int m, vi U, vi V, vi W) {
for(int i = 0;i < m;i++)
edg.PB({W[i], {U[i], V[i]}});
for(int i = 0;i < n;i++)
par[i] = i, siz[i] = 1, postao[i] = INF;
sort(edg.begin(), edg.end());
for(pair < int, pii > cur : edg){
mrg(cur.Y.X, cur.Y.Y, cur.X);
}
}
bool probaj(int x, int y, int z){
x = pr(x, z); y = pr(y, z);
if(x != y)
return 0;
return (z >= postao[x]);
}
int getMinimumFuelCapacity(int x, int y){
int ret = -1;
for(int i = 30;i >= 0;i--)
if(!probaj(x, y, ret + (1 << i)))
ret += (1 << i);
if(ret + 1 == INF)
return -1;
return ret + 1;
}
