#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct UFDS {
int parent;
bool line;
pair<int, int> endpoints;
} Data[N];
vector<pair<pair<int, int>, int> > edge;
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.second < b.second;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < N; i++) {
Data[i].parent = i;
Data[i].line = true;
Data[i].endpoints = {i, i};
}
for(int i = 0; i < M; i++) {
edge.push_back(make_pair(make_pair(U[i], V[i]), W[i]));
}
sort(edge.begin(), edge.end(), cmp);
}
int Find(int x) {
if(Data[x].parent == x)
return x;
return Data[x].parent = Find(Data[x].parent);
}
void Unite(int a, int b) {
int parA = Find(a), parB = Find(b);
if(parA == parB) {
Data[parA].line = false;
Data[parA].endpoints = {-1, -1};
}
else {
Data[parB].parent = parA;
if(!Data[parB].line || !Data[parA].line) {
Data[parA].line = false;
Data[parA].endpoints = {-1, -1};
}
else {
if(Data[parA].endpoints.first != a) {
swap(Data[parA].endpoints.first, Data[parA].endpoints.second);
}
if(Data[parB].endpoints.first != b) {
swap(Data[parB].endpoints.first, Data[parB].endpoints.second);
}
if(a != Data[parA].endpoints.first || b != Data[parB].endpoints.first) {
Data[parA].line = false;
Data[parA].endpoints = {-1, -1};
}
else {
Data[parA].endpoints.first = Data[parB].endpoints.second;
}
}
}
}
void Ini() {
for(int i = 0; i < N; i++) {
Data[i].parent = i;
Data[i].line = true;
Data[i].endpoints = {i, i};
}
}
int getMinimumFuelCapacity(int X, int Y) {
Ini();
//cout << "X = " << X << ", Y = " << Y << "\n";
for(int i = 0; i < edge.size(); i++) {
if(Find(edge[i].first.first) != Find(edge[i].first.second)) {
//cout << "Uniting because of diff components: " << edge[i].first.first << ", " << edge[i].first.second << "\n";
Unite(edge[i].first.first, edge[i].first.second);
}
else if(Data[edge[i].first.first].line) {
//cout << "Uniting because its a line: " << edge[i].first.first << ", " << edge[i].first.second << "\n";
Unite(edge[i].first.first, edge[i].first.second);
}
//else {
//cout << "Not uniting: " << edge[i].first.first << ", " << edge[i].first.second << "\n";
//}
//cout << "Components: " << Find(X) << " " << Find(Y) << "\n";
//cout << "Is it a line? : " << Data[X].line << "\n";
if(Find(X) == Find(Y) && !Data[Find(X)].line) {
return edge[i].second;
}
}
return -1;
}
