#include "swap.h"
#include<bits/stdc++.h>
#include <vector>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 1e6 + 5;
vector<pair<int, int> > g[N];
vector<pair<int, pair<int, int> > > edges;
int mx, n, m, component[N], deg[N], max_deg[N], edg_cnt[N], cnt[N];
bool sb2 = 1, sb1 = 1;
int find(int x){
while(true){
if(x == component[x])
return x;
component[x] = component[component[x]];
x = component[x];
}
}
void merge(int a, int b){
int u = find(a), v = find(b);
deg[a]++;
deg[b]++;
max_deg[v] = max({max_deg[v], max_deg[u], deg[a], deg[b]});
if(v != u)
edg_cnt[v] += edg_cnt[u] + 1;
else
edg_cnt[v]++;
if(u != v)
cnt[v] += cnt[u];
component[u] = v;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
int wut = 0;
map<int, int> mp;
for(int i = 0; i < M; ++i){
int u = U[i], v = V[i], w = W[i];
if(u != 0 and v != 0)
sb2 = false;
g[u].pb({w, v});
g[v].pb({w, u});
mx = max(mx, w);
edges.pb({w, {u ,v}});
mp[u]++;
mp[v]++;
}
for(int i = 0; i < n; ++i)
sort(g[i].begin(), g[i].end());
sort(edges.begin(), edges.end());
for(auto k : mp)
wut = max(wut, k.S);
if(wut > 2)
sb1 = false;
}
int getMinimumFuelCapacity(int X, int Y) {
if(sb2 and m == n - 1){
if(n <= 3) return -1;
if(X == 0){
int x = g[Y][0].F, xx, dest, mn;
if(g[0][0].S != Y){
xx = g[0][0].F;
dest = g[0][0].S;
}else{
xx = g[0][1].F;
dest = g[0][1].S;
}
if(g[0][1].S != Y and g[0][1].S != dest)
mn = g[0][1].F;
else
mn = g[0][2].F;
return max({x, xx, mn});
}
int x = g[X][0].F, xx = g[Y][0].F, mn;
if(g[0][0].S != X and g[0][0].S != Y)
mn = g[0][0].F;
else if(g[0][1].S != X and g[0][1].S != Y)
mn = g[0][1].F;
else
mn = g[0][2].F;
return max({x, xx, mn});
}
if(sb1){
if(m == n - 1)
return -1;
else
return mx;
}
for(int i = 0; i < n; ++i){
component[i] = i;
deg[i] = 0;
max_deg[i] = 0;
edg_cnt[i] = 0;
cnt[i] = 1;
}
for(auto k : edges){
int u = k.S.F, v = k.S.S, c = k.F;
merge(u, v);
// cout << ((max_deg[find(X)] > 2) or (edg_cnt[find(X)] >= cnt[find(X)])) << endl;
if(find(X) == find(Y) and ((max_deg[find(X)] > 2) or (edg_cnt[find(X)] >= cnt[find(X)])))
return c;
}
return -1;
}
