#include "swap.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
vector < vector< pair<ll, ll> > > adj(MAXN);
int sum_dist = 0;
int dist[MAXN];
int par[MAXN], sz[MAXN], edge_sz[MAXN], max_sz[MAXN], cnt[MAXN];
int max_ed = 0, u_max;
int n, m;
vector < pair<int, pair<int, int> > > edges;
int find(int v)
{
if(par[v] == v)
return v;
return par[v] = find(par[v]);
}
void merge(int a, int b)
{
int maxi = max(cnt[a], cnt[b]);
a = find(a), b = find(b);
if(a == b) {
edge_sz[a]++;
max_sz[a] = max(max_sz[a], maxi);
return;
}
if(sz[a] < sz[b])
swap(a, b);
par[b] = a;
sz[a] += sz[b];
edge_sz[a]++;
edge_sz[a] += edge_sz[b];
max_sz[a] = max(max_sz[a], max(max_sz[b], maxi));
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
m = M;
n = N;
for(int i = 0; i < M; i++)
{
adj[U[i]].push_back({W[i], V[i]});
adj[V[i]].push_back({W[i], U[i]});
dist[V[i]] = W[i]; // for sub 2
edges.push_back({W[i], {U[i], V[i]}});
u_max = max(u_max, U[i]);
sum_dist = max(sum_dist, W[i]);
}
sort(edges.begin(), edges.end());
for(int i = 0; i < N; i++)
{
sort(adj[i].begin(), adj[i].end());
max_ed = max(max_ed, (int)adj[i].size());
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(max_ed <= 2) // Sub 1
{
if(m == n - 1)
return -1;
else
return sum_dist;
}
if(u_max == 0) // Sub 2
{
if(X > Y)
swap(X, Y);
ll sum = max(dist[X], dist[Y]);
if(X != 0) {
sum = max(sum, (adj[0][0].second != X && adj[0][0].second != Y) ? adj[0][0].first : ((adj[0][1].second != X && adj[0][1].second != Y) ? adj[0][1].first : adj[0][2].first));
} else
{
sum = max(sum, (adj[0][0].second != Y ? max(adj[0][0].first, adj[0][1].second != Y ? adj[0][1].first : adj[0][2].first) : max(adj[0][1].first, adj[0][2].first)));
}
return sum;
}
//Sub 3, 4
for(int i = 0; i < n; i++)
{
cnt[i] = 0;
edge_sz[i] = max_sz[i] = 0;
sz[i] = 1;
par[i] = i;
}
for(pair<int, pair<int, int> > edge : edges)
{
cnt[edge.second.first]++;
cnt[edge.second.second]++;
merge(edge.second.first, edge.second.second);
if(find(X) == find(Y))
{
int curr = find(X);
if(edge_sz[curr] >= sz[curr] || max_sz[curr] > 2)
return edge.first;
}
}
return -1;
}
