#include "swap.h"
#include <cstring>
#include <vector>
const int N = 100000, M = 200000;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ii[M], jj[M], ww[M];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (ww[hh[j]] == ww[h])
j++;
else if (ww[hh[j]] < ww[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int ds[N]; char ok[N];
int find(int i) {
return ds[i] < 0 ? i : find(ds[i]);
}
void join(int i, int j, char special) {
i = find(i);
j = find(j);
if (i == j) {
ok[i] = 1;
return;
}
if (ds[i] > ds[j])
ds[i] = j, ok[j] |= ok[i] | special;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, ok[i] |= ok[j] | special;
}
}
int hh[M], n, m;
void init(int n_, int m_, std::vector<int> II, std::vector<int> JJ, std::vector<int> WW) {
int h;
n = n_, m = m_;
for (h = 0; h < m; h++)
ii[h] = II[h], jj[h] = JJ[h], ww[h] = WW[h], hh[h] = h;
sort(hh, 0, m);
}
int getMinimumFuelCapacity(int u, int v) {
static int dd[N];
int h;
memset(ds, -1, n * sizeof *ds);
memset(dd, 0, n * sizeof *dd);
memset(ok, 0, n * sizeof *ok);
for (h = 0; h < m; h++) {
int i = ii[hh[h]], j = jj[hh[h]], w = ww[hh[h]];
dd[i]++, dd[j]++;
join(i, j, dd[i] > 2 || dd[j] > 2);
if (find(u) == find(v) && ok[find(u)])
return w;
}
return -1;
}
