#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, w;
};
class dsu {
private: vector<int> p, rank;
public:
dsu(int n) {
p.assign(n, -1);
rank.assign(n, 0);
}
int root(int x) {
if (p[x] == -1) {
return x;
}
return (p[x] = root(p[x]));
}
bool same_set(int x, int y) {
return (root(x) == root(y));
}
void connect(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (rank[x] > rank[y]) {
p[y] = x;
} else {
p[x] = y;
if (rank[x] == rank[y]) {
rank[y]++;
}
}
}
}
};
int n, m, dfs_cnt = 0, max_log;
vector< vector<int> > g;
vector<bool> swappable;
vector<int> dfs_in, dfs_out;
vector< vector<int> > up;
vector<edge> edges;
void dfs(int u, int p) {
//cout << u << endl;
dfs_in[u] = dfs_cnt++;
up[u][0] = p;
for (int i = 1; i <= max_log; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
for (auto& v : g[u]) {
if (v != p) {
dfs(v, u);
}
}
dfs_out[u] = dfs_cnt++;
}
bool is_anc(int u, int v) {
return (dfs_in[u] <= dfs_in[v] && dfs_out[u] >= dfs_out[v]);
}
int lca(int u, int v) {
if (is_anc(u, v)) {
return u;
}
if (is_anc(v, u)) {
return v;
}
for (int i = max_log; i >= 0; i--) {
if (!is_anc(up[u][i], v)) {
u = up[u][i];
}
}
return up[u][0];
}
int first_swappable(int u) {
if (swappable[u]) {
return u;
}
for (int i = max_log; i >= 0; i--) {
if (!swappable[up[u][i]]) {
u = up[u][i];
}
}
if (u == n + m - 1) {
return -1;
}
return up[u][0];
}
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(), [](const edge &a, const edge &b) {
return a.w < b.w;
});
g.resize(n + m);
swappable.assign(n + m, false);
dsu conn(n);
vector<int> deg(n, 0), cc(n);
iota(cc.begin(), cc.end(), 0);
for (int i = 0; i < m; i++) {
int x = edges[i].u, y = edges[i].v;
deg[x]++;
deg[y]++;
if (conn.same_set(x, y)) {
g[cc[conn.root(x)]].push_back(n + i);
g[n + i].push_back(cc[conn.root(x)]);
swappable[n + i] = true;
cc[conn.root(x)] = n + i;
} else {
g[cc[conn.root(x)]].push_back(n + i);
g[cc[conn.root(y)]].push_back(n + i);
g[n + i].push_back(cc[conn.root(x)]);
g[n + i].push_back(cc[conn.root(y)]);
swappable[n + i] = (swappable[cc[conn.root(x)]] || swappable[cc[conn.root(y)]]);
conn.connect(x, y);
cc[conn.root(x)] = n + i;
if (deg[x] >= 3 || deg[y] >= 3) {
swappable[n + i] = true;
}
}
}
max_log = ceil(log2(n + m));
dfs_in.resize(n + m);
dfs_out.resize(n + m);
up.assign(n + m, vector<int>(max_log + 1));
dfs(n + m - 1, n + m - 1);
}
int getMinimumFuelCapacity(int X, int Y) {
int u = first_swappable(lca(X, Y));
if (u == -1) {
return -1;
}
return edges[u - n].w;
}
