#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, pair<int, int> > > brn;
const int dydis = 1e5 + 10;
int tevas[dydis];
int kadaNelinija[dydis];
bool neraLinija[dydis] = {};
vector<int> nodes[dydis];
int A[dydis], B[dydis];
int n, m;
vector<pair<int, int> > gr[dydis];
void add(int a, int b, int w) {
//cout << "brn " << a << " -- " << b << ", w = " << w << endl;
gr[a].push_back({b, w});
gr[b].push_back({a, w});
}
int fp(int v) {
if(tevas[v] == v) return v;
return tevas[v] = fp(tevas[v]);
}
void conn(int a, int b, int t) {
int inA = a; int inB = b;
a = fp(a);
b = fp(b);
// //cout << "jungiu " << inA << "(yra_linija = " << !neraLinija[a] <<") su " << inB << "(yra_linija = " << !neraLinija[b] << ")" << endl;
if(a == b) {
if(neraLinija[a]) return ;
neraLinija[a] = true;
for(auto x : nodes[a]) kadaNelinija[x] = t;
}else {
add(inA, inB, t);
if(neraLinija[a] || neraLinija[b]) {
if(!neraLinija[a]) for(auto x : nodes[a]) kadaNelinija[x] = t;
if(!neraLinija[b]) for(auto x : nodes[b]) kadaNelinija[x] = t;
}
if(nodes[a].size() > nodes[b].size()) swap(a, b);
// a ---> b
if(!neraLinija[a] && !neraLinija[b]) {
set<int> galai = {A[a], B[a], A[b], B[b]};
////cout << "linju galai: "; for(auto x : galai) //cout << x << " ";
// //cout << ", o as jungiu " << inA << " su " << inB << endl;
if(galai.count(inA) && galai.count(inB)) {
/// sujungiau liniju galus
int na, nb;
if(A[a] == inA || A[a] == inB) {
na = B[a];
}else {
na = A[a];
}
if(A[b] == inA || A[b] == inB) {
nb = B[b];
}else {
nb = A[b];
}
A[b] = na;
B[b] = nb;
}else {
for(auto x : nodes[a]) kadaNelinija[x] = t;
for(auto x : nodes[b]) kadaNelinija[x] = t;
neraLinija[b] = true;
}
}
tevas[a] = b;
for(auto x : nodes[a]) nodes[b].push_back(x);
}
}
int dbInd = 0;
int enter[dydis], leave[dydis];
int rotW[dydis], par[dydis];
int h[dydis];
void dfs(int v, int came) {
enter[v] = dbInd++;
par[v] = came;
// //cout << "esi " << v << endl;
for(auto x : gr[v]) {
if(x.first == came) continue;
h[x.first] = h[v] + 1;
rotW[x.first] = x.second;
//cout << "rot[" << x.first << "] = " << x.second << ", T./Y., " << rotW[x.first] << endl;
dfs(x.first, v);
}
leave[v] = dbInd++;
}
const int dd = 20;
int lft[dydis][dd];
int mx[dydis][dd];
void calc() {
for(int i = 0; i < n; i++) {
lft[i][0] = par[i];
//cout << "rotw[" << i << "] = " << rotW[i] << endl;
mx[i][0] = rotW[i];
//cout << "mx[" << i << "][" << 0 << "] = " << mx[i][0] << endl;
}
for(int j = 1; j < dd; j++) {
for(int i = 0; i < n; i++) {
lft[i][j] = lft[lft[i][j-1]][j-1];
}
}
for(int j = 1; j < dd; j++) {
for(int i = 0; i < n; i++) {
mx[i][j] = max(mx[i][j-1], mx[ lft[i][j-1] ][j-1]);
//cout << "mx[" << i << "][" << j << "] = " << mx[i][j] << endl;
}
}
}
bool isAnc(int a, int b) {
return (enter[a] <= enter[b] && leave[b] <= leave[a]);
}
int lca(int a, int b) {
if(isAnc(a, b)) return a;
if(isAnc(b, a)) return b;
for(int i = dd-1; i > -1; i--) {
if(!isAnc(lft[a][i], b)) {
a = lft[a][i];
}
}
return par[a];
}
int mxPerBrn(int a, int kek) {
int ret = 0;
for(int i = dd-1; i > -1; i--) {
if((1 << i) <= kek) {
ret = max(ret, mx[a][i]);
a = lft[a][i];
kek -= (1 << i);
}
}
return ret;
}
int mxInPath(int a, int b) {
int v = lca(a, b);
int kair = mxPerBrn(a, h[a] - h[v]);
int desn = mxPerBrn(b, h[b] - h[v]);
return max(kair, desn);
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
for(int i = 0; i < n; i++) {
tevas[i] = i;
nodes[i] = {i};
A[i] = i; B[i] = i;
neraLinija[i] = false;
kadaNelinija[i] = -1;
}
for(int i = 0; i < m; i++) {
brn.push_back({W[i], {U[i], V[i]}});
}
sort(brn.begin(), brn.end()); /// nuo maz iki did.
for(auto x : brn) {
int a = x.second.first;
int b = x.second.second;
int w = x.first;
conn(a, b, w);
}
h[0] = 0;
dfs(0, 0);
calc();
for(int i = 0; i < n; i++) {
//cout << "virsune nr " << i << " tampa nebe linija, kai w = " << kadaNelinija[i] << endl;
}
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int res = mxInPath(i, j);
//cout << "min max val tarp " << i << " ir " << j << " yra " << res << endl;
}
//cout << endl;
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(kadaNelinija[fp(X)] == -1 || kadaNelinija[fp(Y)] == -1) return -1;
int ret = mxInPath(X, Y);
ret = max(ret, max(kadaNelinija[fp(X)], kadaNelinija[fp(Y)]));
return ret;
}
