#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define re exit(0);
const int maxn = 100009;
int n,m;
struct E {
int u,v,w;
bool operator < (const E & other) {
return w < other.w;
}
} edge[maxn * 2];
//Kruskal reconstruction tree
int root[maxn];
int getroot(int node) {
return (node == root[node] ? node : root[node] = getroot(root[node]));
}
int nodecount;
vector <int> krt[maxn * 2];
int weight[maxn * 2],edgepos[maxn * 2];
pair <int,int> segment[maxn * 2];
pair <int,int> merge(pair <int,int> a,pair <int,int> b) {
if (a.first > a.second) swap(a.first,a.second);
if (b.first > b.second) swap(b.first,b.second);
if (a.first == -1 || b.first == -1) return {-1,-1};
if (a.first == 0) return b;
if (b.first == 0) return a;
if (a.first == b.first && a.second == b.second) return {-1,-1};
if (a.first == b.first) return {a.second,b.second};
if (a.first == b.second) return {a.second,b.first};
if (a.second == b.first) return {a.first,b.second};
if (a.second == b.second) return {a.first,b.first};
return {-1,-1};
}
void dfs(int node) {
//leaf
if (krt[node].empty()) {
segment[node] = {node,node};
return;
}
int index = edgepos[node];
segment[node] = {edge[index].u,edge[index].v};
for (int x : krt[node]) {
dfs(x);
segment[node] = merge(segment[node],segment[x]);
}
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W) {
n = n,m = m;
for (int i = 1;i <= m;i++) edge[i] = {U[i - 1] + 1,V[i - 1] + 1,W[i - 1]};
//build krt
nodecount = n;
sort(edge + 1,edge + 1 + m);
for (int i = 1;i <= n;i++) root[i] = i;
for (int i = 1;i <= m;i++) {
int u = getroot(edge[i].u),v = getroot(edge[i].v);
if (u == v) continue;
nodecount++;
weight[nodecount] = edge[i].w;
edgepos[nodecount] = i;
krt[nodecount].push_back(u);
krt[nodecount].push_back(v);
}
dfs(nodecount);
}
int getMinimumFuelCapacity(int x, int y) {
x++,y++;
return 0;
}
