#include "swap.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int OO = 1e9 + 10;
vector<pii> g[N];
void init(int n, int m,
vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < m; ++i) {
g[U[i]].PB({V[i], W[i]});
g[V[i]].PB({U[i], W[i]});
}
}
int bio[N], sum, siz, tri;
void dfs(int u, int k) {
if(bio[u]) return;
bio[u] = 1;
siz ++;
int cnt = 0;
for(pii e : g[u]) {
if(e.Y <= k) {
dfs(e.X, k);
sum ++;
cnt ++;
}
}
tri = max(tri, cnt);
}
int getMinimumFuelCapacity(int X, int Y) {
int lo = -1, hi = OO;
for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) {
memset(bio, 0, sizeof(bio));
sum = 0;
siz = 0;
tri = 0;
dfs(X, mi);
if((tri >= 3 || siz <= sum / 2) && bio[Y]) { hi = mi; }
else { lo = mi; }
}
return hi == OO ? -1 : hi;
}
