#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100005;
vector<tuple<int, int, int>> edges;
int N, M;
struct Set{
int parent;
bool line;
pair<int, int> tail;
Set(){};
Set(int i){
parent = i;
line = true;
tail = make_pair(i, i);
}
};
Set t[MaxN];
int parent[MaxN];
bool line[MaxN];
pair<int, int> tail[MaxN];
int leader(int x){
return t[x].parent == x ? x : t[x].parent = leader(t[x].parent);
}
void unite(int x, int y){
int X = x, Y = y;
x = leader(x);
y = leader(y);
if (x == y){
t[y].line = false;
return;
}
t[x].parent = y;
if (!t[x].line){
t[y].line = false;
return;
}
if (!t[y].line) return;
if (t[x].tail.first != X && t[x].tail.second != X){
t[y].line = false;
return;
}
if (t[y].tail.first != Y && t[y].tail.second != Y){
t[y].line = false;
return;
}
pair<int, int> new_tail;
new_tail.first = t[x].tail.first ^ t[x].tail.second ^ X;
new_tail.second = t[y].tail.first ^ t[y].tail.second ^ Y;
t[y].tail = new_tail;
}
bool can(int x, int y){
x = leader(x);
y = leader(y);
return x == y && !t[x].line;
}
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.emplace_back(W[i], U[i], V[i]);
}
sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
for (int i = 0; i < N; i++) t[i] = Set(i);
for (auto [w, u, v] : edges){
unite(u, v);
if (can(X, Y)) return w;
}
return -1;
}
