#define _CRT_SECURE_NO_WARNINGS
#include "swap.h"
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <string>
#include <cstring>
#include <algorithm>
#include <random>
#include <chrono>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cassert>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
const int N = 100005;
const ll oo = 1000000000000000, MOD = 1000000007;
vector<pair<int, int>> g[N];
int timer, tin[N], tout[N], up_node[N][23], par[N], n, m;
ll mx_edge[N][23], mn_adj_edge[N][23];
map<pair<int, int>, int> weight_of_edge;
set<pair<ll, int>> st[N];
void dfs(int u, int p) {
++timer;
tin[u] = timer;
par[u] = p;
if (u != 1) {
up_node[u][0] = p;
mx_edge[u][0] = weight_of_edge[{u, p}];
ll mn = oo;
for (auto num : st[p]) {
if (num.sc != par[p] && num.sc != u) {
mn = min(mn, (ll)num.fr);
break;
}
}
mn_adj_edge[u][0] = mn;
for (int i = 1; i <= 20; ++i) {
up_node[u][i] = up_node[up_node[u][i - 1]][i - 1];
mx_edge[u][i] = max(mx_edge[up_node[u][i - 1]][i - 1], mx_edge[u][i - 1]);
mn_adj_edge[u][i] = min(mn_adj_edge[up_node[u][i - 1]][i - 1], mn_adj_edge[u][i - 1]);
}
}
for (auto num : g[u]) {
st[u].insert({ num.sc,num.fr });
}
for (auto num : g[u]) {
if (num.fr != p) {
dfs(num.fr, u);
}
}
++timer;
tout[u] = timer;
}
bool upper(int x, int y) {
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
pair<ll, ll> chari_mx_mn(int x, int y,int type) {
int x1 = x;
ll mx = 0;
ll mn = oo;
for (int i = 20; i >= 0; --i) {
if (up_node[x1][i] != 0) {
if (upper(up_node[x1][i], y) != 1) {
mx = max(mx, mx_edge[x1][i]);
mn = min(mn, mn_adj_edge[x1][i]);
x1 = up_node[x1][i];
}
}
}
mx = max(mx, mx_edge[x1][0]);
int lc = up_node[x1][0];
int qan = 0;
if (type == 0) {
for (auto num : st[lc]) {
++qan;
assert(qan <= 10);
if (par[lc] == num.sc) {
mn = min(mn, num.fr);
break;
}
if (upper(num.sc, x) == 0 && upper(num.sc, y) == 0) {
mn = min(mn, num.fr);
break;
}
}
}
return { mx,mn };
}
pair<ll,ll> lca_mx_mn(int x, int y) {
if (upper(x, y)) {
pair<ll,ll> p1 = chari_mx_mn(y, x,1);
int cnt = 0;
for (auto num : st[y]) {
if (num.sc != par[y]) {
++cnt;
if (cnt == 2) {
p1.fr = min(p1.fr, num.fr);
break;
}
}
}
cnt = 0;
for (auto num : st[x]) {
if (num.sc == par[x]) {
++cnt;
if (cnt == 2) {
p1.fr = min(p1.fr, num.fr);
break;
}
}
else {
if (upper(num.sc, y) == 0) {
++cnt;
if (cnt == 2) {
p1.fr = min(p1.fr, num.fr);
break;
}
}
}
}
return p1;
}
if (upper(y, x)) {
pair<ll, ll> p1 = chari_mx_mn(x, y,1);
int cnt = 0;
for (auto num : st[x]) {
if (num.sc != par[x]) {
++cnt;
if (cnt == 2) {
p1.fr = min(p1.fr, num.fr);
break;
}
}
}
cnt = 0;
for (auto num : st[y]) {
if (num.sc == par[y]) {
++cnt;
if (cnt == 2) {
p1.fr = min(p1.fr, num.fr);
break;
}
}
else {
if (upper(num.sc, x) == 0) {
++cnt;
if (cnt == 2) {
p1.fr = min(p1.fr, num.fr);
break;
}
}
}
}
return p1;
}
pair<ll, ll> p1 = chari_mx_mn(x, y,0);
pair<ll, ll> p2 = chari_mx_mn(y, x, 0);
ll mx = max(p1.fr, p2.fr);
ll mn = min(p1.sc, p2.sc);
int cnt = 0;
for (auto num : st[x]) {
if (num.sc != par[x]) {
++cnt;
if (cnt == 2) {
mn = min(mn, num.fr);
break;
}
}
}
cnt = 0;
for (auto num : st[y]) {
if (num.sc != par[y]) {
++cnt;
if (cnt == 2) {
mn = min(mn, num.fr);
break;
}
}
}
return { mx,mn };
}
vector<pair<int , int>> ynd;
void init(int n1, int m1,vector<int> U, vector<int> V, vector<int> W) {
n = n1;
m = m1;
for (int i = 0; i < m; ++i) {
U[i]++;
V[i]++;
g[U[i]].pb({ V[i],W[i] });
g[V[i]].pb({ U[i],W[i] });
weight_of_edge[{U[i], V[i]}] = W[i];
weight_of_edge[{V[i], U[i]}] = W[i];
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= 20; ++j) {
mn_adj_edge[i][j] = oo;
mx_edge[i][j] = 0;
}
}
//dfs(1, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
++X;
++Y;
pair<ll, ll> p1 = lca_mx_mn(X, Y);
//cout << "CLNG "<< p1.fr << " " << p1.sc << endl;
if (p1.sc == oo) {
return -1;
}
return max(p1.fr, p1.sc);
}
