#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], dp[N], up_mn_dp[N][23];
map<pair<int, int>, int> weight_of_edge;
set<pair<ll, int>> st[N];
pair<int, ll> erkrord_amenamec(int u,int ty) {
int cnt = 0;
for (auto num : st[u]) {
if (ty == 1) {
if (num.sc != par[u]) {
++cnt;
if (cnt == 2) {
return { num.sc,num.fr };
}
}
}
else {
++cnt;
if (cnt == 2) {
return { num.sc,num.fr };
}
}
}
return { -1,oo };
}
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) {
dp[u] = min(max(dp[num.fr], (ll)num.sc), dp[u]);
dfs(num.fr, u);
}
}
pair<int, ll> p1 = erkrord_amenamec(u, 1);
if (p1.fr != -1) {
dp[u] = min(dp[u], p1.sc);
}
++timer;
tout[u] = timer;
}
void jnjel(int u, int v) {
st[u].erase({ weight_of_edge[{u,v}],v });
}
void avelacnel(int u, int v) {
st[u].insert({ weight_of_edge[{u,v}],v });
}
void dfs_dp(int u, int p) {
if (u != 1) {
jnjel(p, u);
pair<int, ll> p1 = erkrord_amenamec(p, 2);
up_mn_dp[u][0] = max(p1.sc, (ll)weight_of_edge[{u, p}]);
for (auto num : st[p]) {
up_mn_dp[u][0] = min(up_mn_dp[u][0], max(max(dp[num.sc], (ll)num.fr),(ll)weight_of_edge[{u,p}]));
break;
}
avelacnel(p, u);
for (int i = 1; i <= 20; ++i) {
int x = up_node[u][i - 1];
up_mn_dp[u][i] = min(up_mn_dp[u][i - 1], max(mx_edge[u][i - 1], up_mn_dp[x][i - 1]));
}
}
for (auto num : g[u]) {
if (num.fr != p) {
dfs_dp(num.fr, u);
}
}
}
bool upper(int x, int y) {
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
pair<pair<ll,ll>,int> 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 },x1 };
}
ll lifting_dp(int u1) {
int u = u1;
ll mn = oo;
for (int j = 20; j >= 0; --j) {
if (up_node[u][j] != 0) {
mn = min(mn, up_mn_dp[u][j]);
u = up_node[u][j];
}
}
return mn;
}
pair<pair<ll, ll>, int> xzz(int x,int y,pair<pair<ll,ll>,int> p1) {
jnjel(x, p1.sc);
ll mn = erkrord_amenamec(x, 2).sc;
mn = min(mn, lifting_dp(x));
avelacnel(x, p1.sc);
jnjel(y, par[y]);
mn = min(mn, erkrord_amenamec(y, 2).sc);
for (auto num : st[y]) {
mn = min(mn,max(dp[num.sc], (ll)num.fr));
break;
}
avelacnel(y, par[y]);
p1.fr.sc = min(p1.fr.sc, mn);
return p1;
}
pair<ll,ll> lca_mx_mn(int x, int y) {
if (upper(x, y)) {
pair<pair<ll,ll>,int> p1 = chari_mx_mn(y, x, 1);
p1 = xzz(x, y, p1);
return p1.fr;
}
if (upper(y, x)) {
pair<pair<ll, ll>, int> p1 = chari_mx_mn(x, y, 1);
p1 = xzz(y, x, p1);
return p1.fr;
}
pair<pair<ll, ll>, int> p1 = chari_mx_mn(x, y,0);
pair<pair<ll, ll>, int> p2 = chari_mx_mn(y, x, 0);
ll mx = max(p1.fr.fr, p2.fr.fr);
ll mn = min(p1.fr.sc, p2.fr.sc);
jnjel(x, par[x]);
mn = min(mn, erkrord_amenamec(x, 2).sc);
for (auto num : st[x]) {
mn = min(mn, max(dp[num.sc], (ll)num.fr));
break;
}
avelacnel(x, par[x]);
jnjel(y, par[y]);
mn = min(mn, erkrord_amenamec(y, 2).sc);
for (auto num : st[y]) {
mn = min(mn, max(dp[num.sc], (ll)num.fr));
break;
}
avelacnel(y, par[y]);
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) {
dp[i] = oo;
for (int j = 0; j <= 20; ++j) {
mn_adj_edge[i][j] = oo;
mx_edge[i][j] = 0;
up_mn_dp[i][j] = oo;
}
}
dfs(1, 0);
dfs_dp(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);
}
