#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int BIG = 1e9 + 7; //
int second[100001];
int third[100001];
int depth[100001];
int parent[100001];
int parWeight[100001];
int liftWt[100001][20]; // The maximum of weights when going above
int liftVal[100001][20]; // The vertex that is 2^i above
int liftMin[100001][20]; // The minimum of the thirds up to 2^i above
vector<vector<pair<int, int>>> adj;
void dfs(int n, int par = -1) {
for(auto p : adj[n]) {
int ch, w;
tie(ch, w) = p;
if(ch == par) continue;
parWeight[ch] = w;
parent[ch] = n;
depth[ch] = depth[n] + 1;
dfs(ch, n);
}
}
struct dsu {
vector<int> par, siz, lin, linen;
void init(int n) {
par.resize(n);
siz.resize(n, 1);
lin.resize(n, BIG);
linen.resize(n, 1);
for(int i = 0; i < n; i++) par[i] = i;
}
int get(int x) {
if(par[x] == x) return x;
int g = get(par[x]);
if(lin[x] != BIG) return par[x] = g;
if(lin[par[x]] != BIG) {
lin[x] = lin[par[x]];
linen[x] = 0;
}
return par[x] = g;
}
bool unite(int x, int y, int w) {
int gx = get(x), gy = get(y);
if(gx == gy) {
if(lin[gx] == BIG) {
lin[gx] = w;
linen[gx] = 0;
}
return false;
}
// Connecting a line and a line, becomes a line
if(lin[gx] == BIG && lin[gy] == BIG && linen[x] && linen[y]) {
if(siz[gx] != 1) linen[x] = 0;
if(siz[gy] != 1) linen[y] = 0;
}
// Connecting a line and a line, doesn't become a line
else {
lin[gx] = min(lin[gx], w);
lin[gy] = min(lin[gy], w);
linen[x] = linen[y] = 0;
}
x = gx; y = gy;
if(siz[x] > siz[y]) swap(x, y);
par[x] = y;
siz[y] += siz[x];
return true;
}
};
dsu uf;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<pair<int, pair<int, int>>> edges(M);
for(int i = 0; i < N; i++) {
depth[i] = 0;
second[i] = BIG;
third[i] = -1;
parent[i] = 0;
}
adj.resize(N);
for(int i = 0; i < M; i++) {
edges[i] = {W[i], {U[i], V[i]}};
}
sort(edges.begin(), edges.end());
uf.init(N);
for(auto [w, p] : edges) {
int u, v;
tie(u, v) = p;
if(third[u] < 0) {
third[u]--;
if(third[u] == -3) second[u] = w;
if(third[u] == -4) third[u] = w;
}
if(third[v] < 0) {
third[v]--;
if(third[v] == -3) second[v] = w;
if(third[v] == -4) third[v] = w;
}
if(uf.unite(u, v, w)) {
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
for(int i = 0; i < N; i++) {
uf.get(i);
// cout << i << ' ' << uf.lin[i] << endl;
if(third[i] < 0) third[i] = BIG;
}
dfs(0);
for(int i = 0; i < 20; i++) {
liftWt[0][i] = liftVal[0][i] = 0;
liftMin[0][i] = third[0];
}
for(int x = 1; x < N; x++) {
liftWt[x][0] = parWeight[x];
liftVal[x][0] = parent[x];
liftMin[x][0] = min(third[x], third[parent[x]]);
}
for(int i = 1; i < 20; i++) {
for(int x = 1; x < N; x++) {
int xUp = liftVal[x][i-1];
liftWt[x][i] = max(liftWt[x][i-1], liftWt[xUp][i-1]);
liftVal[x][i] = liftVal[xUp][i-1];
liftMin[x][i] = min(liftMin[x][i-1], liftMin[xUp][i-1]);
}
}
}
int getMinimumFuelCapacity(int x, int y) {
int weightMax = 0, thirdMin = BIG;
int secondx = uf.lin[x], secondy = uf.lin[y];
if(depth[x] > depth[y]) swap(x, y);
if(depth[x] < depth[y]) {
int g = depth[y] - depth[x];
for(int i = 0; i < 20; i++) {
if(g & (1 << i)) {
weightMax = max(weightMax, liftWt[y][i]);
thirdMin = min(thirdMin, liftMin[y][i]);
y = liftVal[y][i];
}
}
}
for(int i = 19; i >= 0; i--) {
if(liftVal[x][i] != liftVal[y][i]) {
weightMax = max(weightMax, liftWt[x][i]);
thirdMin = min(thirdMin, liftMin[x][i]);
x = liftVal[x][i];
weightMax = max(weightMax, liftWt[y][i]);
thirdMin = min(thirdMin, liftMin[y][i]);
y = liftVal[y][i];
}
if(i == 0 && x != y) {
weightMax = max(weightMax, liftWt[x][i]);
thirdMin = min(thirdMin, liftMin[x][i]);
x = liftVal[x][i];
weightMax = max(weightMax, liftWt[y][i]);
thirdMin = min(thirdMin, liftMin[y][i]);
y = liftVal[y][i];
}
}
int ans = max(weightMax, min(thirdMin, min(secondx, secondy)));
if(ans == BIG) return -1;
return ans;
}
