#include "swap.h"
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);
typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;
using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);
const int max_N = 100005;
vector<pii> inf[max_N];
vi g[max_N];
int sz[max_N], p[max_N], type[max_N], adj_cnt[max_N];
int n, m, timer;
vector<pair<int, pii>> edges = { {0,{0,0}} };
void make_set(int x) {
g[x] = { x };
p[x] = x;
sz[x] = 1;
}
int find_set(int x) {
if (p[x] == x) return x;
return p[x] = find_set(p[x]);
}
void fill_information(int set_index, int new_set) {
for (auto node : g[set_index]) {
inf[node].pub({ timer,new_set });
}
}
void union_sets(int x, int y, int w) {
++adj_cnt[x];
++adj_cnt[y];
int x_set = find_set(x), y_set = find_set(y);
if (x_set == y_set) {
if (type[x_set]) return;
type[x_set] = 1;
fill_information(x_set, x_set);
return;
}
if (sz[x_set] < sz[y_set]) {
swap(x_set, y_set);
}
sz[x_set] += sz[y_set];
p[y_set] = x_set;
if (!type[x_set] && (type[y_set] || adj_cnt[x] >= 3 || adj_cnt[y] >= 3)) {
type[x_set] = 1;
fill_information(x_set, x_set);
}
if (type[x_set]) {
fill_information(y_set, x_set);
}
for (auto node : g[y_set]) {
g[x_set].pub(node);
}
}
void init(int N, int M, vi U, vi V, vi W) {
n = N, m = M;
for (int i = 0; i < n; ++i) {
make_set(i);
}
for (int i = 0; i < m; ++i) {
edges.pub({ W[i],{U[i],V[i]} });
}
sort(all(edges));
for (auto opt : edges) {
if (opt.ff == 0) continue;
++timer;
int x = opt.ss.ff;
int y = opt.ss.ss;
int w = opt.ff;
union_sets(x, y, w);
}
}
int find_minimum(int x, int y) {
int l = 0, r = (int)inf[x].size() - 1, mid;
int ret = MAX;
while (l <= r) {
mid = (l + r) / 2;
int jam = inf[x][mid].ff;
int x_set = inf[x][mid].ss;
int ind = lower_bound(all(inf[y]), mpr(inf[x][mid].ff, -1)) - inf[y].begin() - 1;
if (ind >= 0 && ind < (int)inf[y].size() && inf[y][ind].ss == x_set) {
ret = min(ret, max(edges[jam].ff, edges[inf[y][mid].ff].ff));
r = mid - 1;
continue;
}
++ind;
if (ind >= 0 && ind < (int)inf[y].size() && inf[y][ind].ss == x_set) {
ret = min(ret, max(edges[jam].ff, edges[inf[y][mid].ff].ff));
r = mid - 1;
continue;
}
l = mid + 1;
}
return ret;
}
int getMinimumFuelCapacity(int X, int Y) {
int x = X, y = Y;
int ans = min(find_minimum(x, y), find_minimum(y, x));
return (ans == MAX ? -1 : ans);
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/
/*
3 2
0 1 5
0 2 5
1
1 2
*/
