#include "swap.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
using pii = pair < int, int >;
struct edge {
int v1, v2, w;
};
struct bamboo {
bool isBamboo;
int L, R;
int c1, c2;
int w1, w2;
bamboo() {
isBamboo = true;
L = -1;
R = -1;
c1 = 0;
c2 = 0;
w1 = 0;
w2 = (int)1e9 + 7;
}
bamboo(bool isBamboo, int L, int R, int w1, int w2) {
this->isBamboo = isBamboo;
this->L = L;
this->R = R;
c1 = 0;
c2 = 0;
this->w1 = w1;
this->w2 = w2;
}
};
bamboo merge(bamboo v1, bamboo v2, edge e) {
if (v1.isBamboo && v2.isBamboo) {
if (e.v1 == v1.L && e.v2 == v2.L) return { true, v1.R, v2.R, e.w, (int)1e9 };
if (e.v1 == v1.L && e.v2 == v2.R) return { true, v1.R, v2.L, e.w, (int)1e9 };
if (e.v1 == v1.R && e.v2 == v2.L) return { true, v1.L, v2.R, e.w, (int)1e9 };
if (e.v1 == v1.R && e.v2 == v2.R) return { true, v1.L, v2.L, e.w, (int)1e9 };
swap(e.v1, e.v2);
if (e.v1 == v1.L && e.v2 == v2.L) return { true, v1.R, v2.R, e.w, (int)1e9 };
if (e.v1 == v1.L && e.v2 == v2.R) return { true, v1.R, v2.L, e.w, (int)1e9 };
if (e.v1 == v1.R && e.v2 == v2.L) return { true, v1.L, v2.R, e.w, (int)1e9 };
if (e.v1 == v1.R && e.v2 == v2.R) return { true, v1.L, v2.L, e.w, (int)1e9 };
return { false, -1, -1, e.w, (int)1e9 };
}
return { false, -1, -1, e.w, (int)1e9 };
}
bool cmp(edge e1, edge e2) {
return e1.w < e2.w;
}
int timer;
vector < vector < int > > v;
vector < int > tin, tout;
vector < vector < pii > > binJ;
vector < bool > r;
vector < int > comp;
vector < bamboo > values;
bool isPar(int v1, int v2) {
return tin[v1] <= tin[v2] && tout[v2] <= tout[v1];
}
int lca(int v1, int v2) {
if (isPar(v1, v2)) return v1;
if (isPar(v2, v1)) return v2;
for (int j = 19; j >= 0; j--) {
if (!isPar(binJ[j][v1].first, v2)) v1 = binJ[j][v1].first;
}
if (binJ[0][v1].first == v1 && !isPar(v1, v2)) return -1;
return binJ[0][v1].first;
}
void dfs(int val, int prev) {
tin[val] = ++timer;
binJ[0][val] = { prev, values[val].w2 };
for (int j = 1; j < 20; j++) {
binJ[j][val].first = binJ[j - 1][binJ[j - 1][val].first].first;
binJ[j][val].second = min(binJ[j - 1][val].second, binJ[j - 1][binJ[j - 1][val].first].second);
}
for (auto to : v[val]) {
dfs(to, val);
}
tout[val] = timer;
}
int getComp(int val) {
if (val == comp[val]) return val;
return comp[val] = getComp(comp[val]);
}
void init(int n, int m, vector < int > v1, vector < int > v2, vector < int > w) {
vector < edge > edges(m);
for (int i = 0; i < m; i++) {
edges[i].v1 = v1[i];
edges[i].v2 = v2[i];
edges[i].w = w[i];
}
sort(edges.begin(), edges.end(), cmp);
int allNodes = n;
binJ.resize(20, vector < pii >(2 * n));
tin.resize(2 * n);
tout.resize(2 * n);
v.resize(2 * n);
values.resize(2 * n);
comp.resize(2 * n);
r.resize(2 * n, true);
for (int i = 0; i < 2 * n; i++) comp[i] = i;
for (int i = 0; i < 2 * n; i++) {
values[i] = { true, i, i, 0, (int)1e9};
}
for (int i = 0; i < edges.size(); i++) {
int t1 = getComp(edges[i].v1);
int t2 = getComp(edges[i].v2);
if (t1 == t2) {
if (edges[i].v1 != values[t1].L &&
edges[i].v1 != values[t1].R &&
edges[i].v2 != values[t1].L &&
edges[i].v2 != values[t1].R )
{
values[t1].w2 = min(values[t1].w2, edges[i].w);
}
if(edges[i].v1 == values[t1].L && edges[i].v2 == values[t1].R) values[t1].w2 = min(values[t1].w2, edges[i].w);
if(edges[i].v2 == values[t1].L && edges[i].v1 == values[t1].R) values[t1].w2 = min(values[t1].w2, edges[i].w);
if (edges[i].v1 == values[t1].L || edges[i].v2 == values[t1].L) values[t1].c1++;
if (edges[i].v1 == values[t1].R || edges[i].v2 == values[t1].R) values[t1].c2++;
if(values[t1].c1 >= 2 || values[t2].c2 >= 2) min(values[t1].w2, edges[i].w);
continue;
}
//cout << "DEBUG:: " << allNodes << " " << t1 << " " << t2 << " WEIGHT " << edges[i].w << endl;
v[allNodes].push_back(t1);
v[allNodes].push_back(t2);
comp[t1] = allNodes;
comp[t2] = allNodes;
r[t1] = false;
r[t2] = false;
values[allNodes] = merge(values[t1], values[t2], edges[i]);
allNodes++;
}
timer = 0;
for (int i = 0; i < allNodes; i++) {
if (r[i]) {
dfs(i, i);
}
}
}
int getMinimumFuelCapacity(int x, int y) {
int p = lca(x, y);
if (p == -1) return -1;
int w2 = 1e9 + 7;
for (int j = 19; j >= 0; j--) {
if (values[binJ[j][p].first].isBamboo) {
w2 = min(w2, binJ[j][p].second);
p = binJ[j][p].first;
}
}
w2 = min(w2, values[p].w2);
if (binJ[0][p].first == p && values[p].isBamboo && w2 == 1e9 + 7) return -1;
int res = w2;
if (!values[p].isBamboo) res = min(res, values[p].w1);
p = binJ[0][p].first;
//cout << p << " " << values[p].w1 << " " << res << endl;
if (!values[p].isBamboo) res = min(res, values[p].w1);
return res;
}
