#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 1e5 + 5;
vector<array<int, 2>> e[MXN];
vector<array<int, 2>> cnt[4][MXN];
int val(vector<array<int, 2>> &v, int t)
{
return (*prev(upper_bound(v.begin(), v.end(), array<int, 2>{t, inf})))[1];
}
int get(int x, int t)
{
int p = val(e[x], t);
if (p < 0) return x;
return get(p, t);
}
void inc(int x, int d, int t)
{
if (d >= 3) return;
x = get(x, t);
cnt[d][x].push_back({t, val(cnt[d][x], t) - 1});
cnt[d + 1][x].push_back({t, val(cnt[d + 1][x], t) + 1});
}
void unite(int x, int y, int t)
{
x = get(x, t), y = get(y, t);
if (x == y) return;
if (val(e[x], t) > val(e[y], t)) swap(x, y);
e[x][0][1] += e[y][0][1];
e[y].push_back({t, x});
for (int i = 0; i < 4; i++)
{
cnt[i][x].push_back({t, val(cnt[i][x], t) + val(cnt[i][y], t)});
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
for (int i = 0; i < N; i++)
{
e[i] = {{-inf, -1}};
for (int j = 0; j < 4; j++) cnt[j][i] = {{-inf, 0}};
cnt[0][i][0][1] = 1;
}
vector<array<int, 3>> ed;
for (int i = 0; i < U.size(); i++) ed.push_back({W[i], U[i], V[i]});
sort(ed.begin(), ed.end());
vector<int> deg(N, 0);
for (auto &[t, u, v] : ed)
{
unite(u, v, t);
inc(u, deg[u]++, t);
inc(v, deg[v]++, t);
}
}
int getMinimumFuelCapacity(int X, int Y)
{
int l = 0, r = inf;
while (l < r)
{
int mid = (l + r) >> 1;
if (get(X, mid) != get(Y, mid))
{
l = mid + 1;
continue;
}
int R = get(X, mid);
if (val(cnt[1][R], mid) != 2 || val(cnt[3][R], mid)) r = mid;
else l = mid + 1;
}
return (l == inf ? -1 : l);
}
