#include "swap.h"
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 300005;
int parent[MAXN], deg[MAXN];
bool is_good[MAXN]; // Komponentda o'rin almashish imkoni bormi?
int tree_p[MAXN][20], tree_val[MAXN], depth[MAXN];
int n_ptr;
struct Edge {
int u, v, w;
};
bool compareEdges(Edge a, Edge b) {
return a.w < b.w;
}
int find(int i) {
if (parent[i] == i) return i;
return parent[i] = find(parent[i]);
}
vector<int> adj[MAXN];
void dfs(int u, int p, int d) {
tree_p[u][0] = p;
depth[u] = d;
for (int i = 1; i < 20; i++)
tree_p[u][i] = tree_p[tree_p[u][i - 1]][i - 1];
for (int v : adj[u]) dfs(v, u, d + 1);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
vector<Edge> edges;
for (int i = 0; i < M; i++) edges.push_back({U[i], V[i], W[i]});
sort(edges.begin(), edges.end(), compareEdges);
for (int i = 0; i < N + M; i++) {
parent[i] = i;
deg[i] = 0;
is_good[i] = false;
}
n_ptr = N;
for (auto &e : edges) {
int root_u = find(e.u);
int root_v = find(e.v);
int new_node = n_ptr++;
tree_val[new_node] = e.w;
deg[e.u]++; deg[e.v]++;
bool currently_good = (is_good[root_u] || is_good[root_v] || root_u == root_v || deg[e.u] >= 3 || deg[e.v] >= 3);
parent[root_u] = new_node;
adj[new_node].push_back(root_u);
if (root_u != root_v) {
parent[root_v] = new_node;
adj[new_node].push_back(root_v);
}
is_good[new_node] = currently_good;
parent[new_node] = new_node;
}
for (int i = n_ptr - 1; i >= 0; i--) {
if (depth[i] == 0) dfs(i, i, 1);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int u = X, v = Y;
// LCA topish
if (depth[u] < depth[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (depth[tree_p[u][i]] >= depth[v]) u = tree_p[u][i];
}
if (u != v) {
for (int i = 19; i >= 0; i--) {
if (tree_p[u][i] != tree_p[v][i]) {
u = tree_p[u][i];
v = tree_p[v][i];
}
}
u = tree_p[u][0];
}
// LCA dan tepaga qarab birinchi "is_good" tugunni qidiramiz
int curr = u;
for (int i = 19; i >= 0; i--) {
if (tree_p[curr][i] != -1 && !is_good[tree_p[curr][i]])
curr = tree_p[curr][i];
}
curr = tree_p[curr][0];
if (!is_good[curr]) return -1;
return tree_val[curr];
}
