#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using Edge = array<int, 3>;
const int maxn = 1e5 + 5;
struct DSU {
int n;
vector<int> par, size;
DSU(int _n) {
n = _n + 1;
par.resize(n+1);
size.resize(n+1, 1);
for(int i=1; i<=n; i++) par[i] = i;
}
int find(int u) {
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
bool uni(int a, int b) {
a = find(a), b = find(b);
if(a == b) return 0;
if(size[a] < size[b]) swap(a, b);
size[a] += size[b];
par[b] = a;
return 1;
}
bool same_set(int a, int b) { return find(a) == find(b); }
};
int n, m;
vector<Edge> edges;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N; m = M;
for(int i=0; i<m; i++) edges.push_back({ U[i], V[i], W[i] });
sort(edges.begin(), edges.end(), [&](Edge &a, Edge &b) { return a[2] < b[2]; });
}
int getMinimumFuelCapacity(int X, int Y) {
int l=2, r=m-1, ans=-1;
while(l <= r) {
int mid = (l + r) / 2;
DSU dsu(n);
vector<int> deg(n);
for(int i=0; i<=mid; i++) {
dsu.uni(edges[i][0], edges[i][1]);
deg[edges[i][0]]++; deg[edges[i][1]]++;
}
bool line = false;
vector<int> cnt(n);
int mx = 0;
for(int i=0; i<n; i++) {
if(dsu.find(i) != dsu.find(X)) continue;
cnt[deg[i]]++;
mx = max(mx, deg[i]);
}
if(mx <= 2 && cnt[1] == 2) line = 1;
if(dsu.same_set(X, Y) && !line) ans = mid, r = mid - 1;
else l = mid + 1;
}
return (ans == -1 ? ans : edges[ans][2]);
}
