#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <pair <int, int>>> adj;
vector <array <int, 3>> edges;
int n, m;
bool comp(array <int, 3> a, array <int, 3> b) {
return a[2] < b[2];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
adj.resize(N+1);
n = N;
m = M;
for (int i = 0; i < M; i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
edges.push_back({U[i], V[i], W[i]});
}
sort(edges.begin(), edges.end(), comp);
}
struct DSU {
vector <int> link, sz;
vector <bool> cycle, connected;
DSU (int s) {
link = sz = vector <int> (s+1);
connected = cycle = vector <bool> (s+1);
for (int i = 1; i <= s; i++) {
link[i] = i;
sz[i] = 1;
}
}
int head(int x) {
if (link[x] != x)
return link[x] = head(link[x]);
return x;
}
bool same(int a, int b) {
return head(a) == head(b);
}
void unite(int a, int b) {
a = head(a);
b = head(b);
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
link[b] = a;
if (cycle[b])
cycle[a] = true;
if (connected[b])
connected[a] = true;
// cycle[a] |= cycle[b];
}
};
int getMinimumFuelCapacity(int x, int y) {
DSU dsu(n+1);
vector <int> connected(n);
for (int i = 0; i < m; i++) {
int a = edges[i][0], b = edges[i][1];
if (!dsu.same(a, b)) {
dsu.unite(a, b);
connected[a]++;
connected[b]++;
}
else {
dsu.cycle[dsu.head(a)] = true;
connected[a]++;
connected[b]++;
if (dsu.same(a, x)) {
if (dsu.same(x, y)) {
return edges[i][2];
}
}
}
if (connected[a] >= 3)
dsu.connected[dsu.head(a)] = true;
if (connected[b] >= 3)
dsu.connected[dsu.head(b)] = true;
if (dsu.same(x, y) && dsu.cycle[dsu.head(a)] && dsu.same(x, a))
return edges[i][2];
if (dsu.same(x, y)) {
if (dsu.same(x, a) && dsu.connected[dsu.head(x)])
return edges[i][2];
}
}
return -1;
}
// int main() {
// int N, M;
// cin >> N >> M;
// vector <int> u(M), v(M), w(M);
// for (int i = 0; i < M; i++)
// cin >> u[i] >> v[i] >> w[i];
// init(N, M, u, v, w);
// int q;
// cin >> q;
// while (q--) {
// int x, y;
// cin >> x >> y;
// cout << getMinimumFuelCapacity(x, y) << '\n';
// }
// }
