#include "bits/stdc++.h"
#ifndef CYN_LOCAL_INCLUDED
#include "swap.h"
#endif
#pragma region header
using llint = long long int; // 64 bit
using usize = size_t;
using isie = ptrdiff_t;
template <class T>
using Vec = std::vector<T>;
template <class T, size_t N>
using Arr = std::array<T, N>;
template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div;
constexpr int infi32 = infty<int, 2>; // 1073741823
constexpr llint infi64 = infty<llint, 4>; // 2305843009213693951
// infi32 / 2 < 10^9
// infi64 / 2 < 2 * 10^18
constexpr char endl = '\n'; // std::endl without flush ('\n')
inline int popcount(unsigned long long x) noexcept {
#if __cplusplus >= 202002L
return std::popcount(x); // C++20
#else
x = x - ((x >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0x0000007f;
#endif
}
template <class T>
constexpr bool setmin(T& a, const T b) noexcept {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
constexpr bool setmax(T& a, const T b) noexcept {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T>
constexpr T difrc(const T a, const T b) noexcept {
return a > b ? a - b : b - a;
}
class range {
using value_type = int;
struct range_iterator {
value_type itr;
constexpr range_iterator(const value_type pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const range_iterator& other) const noexcept {
return itr != other.itr;
}
constexpr value_type operator*() const noexcept { return itr; }
};
const range_iterator first, last;
public:
constexpr range(const value_type first_, const value_type last_) noexcept
: first(first_), last(last_) {} // [l, r)
constexpr range_iterator begin() const noexcept { return first; }
constexpr range_iterator end() const noexcept { return last; }
};
template <class T>
class span {
using iterator_type = typename std::vector<T>::iterator;
iterator_type first, last;
public:
span(std::vector<T>& v, const usize l, const usize r) noexcept
: first(v.begin() + l), last(v.begin() + r) {} // [l, r)
auto begin() const noexcept { return first; }
auto end() const noexcept { return last; }
};
template <class F>
class rec_lambda {
F f;
public:
explicit constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
template <class... Args>
constexpr auto operator()(Args&&... args) const {
return f(*this, std::forward<Args>(args)...);
}
};
#pragma endregion
class partially_persistent_UnionFind {
std::vector<int> par, last;
std::vector<int> edge;
std::vector<int> deg;
std::vector<std::vector<std::tuple<int, int, int, int>>> history;
public:
partially_persistent_UnionFind() = default;
partially_persistent_UnionFind(int n)
: par(n, -1), last(n, -1), history(n), edge(n, 0), deg(n, 0) {
for (auto& vec : history) vec.emplace_back(-1, -1, 0, 0);
}
int root(int t, int x) {
if (last[x] == -1 || t < last[x]) return x;
return root(t, par[x]);
}
bool same(int t, int x, int y) { return root(t, x) == root(t, y); }
bool merge(int t, int x, int y) {
++deg[x];
++deg[y];
int memo1 = x, memo2 = y;
x = root(t, x);
y = root(t, y);
++edge[x];
if (x == y) {
history[x].emplace_back(
t, par[x], edge[x],
std::max({std::get<3>(history[x].back()), deg[memo1], deg[memo2]}));
return false;
}
if (par[x] > par[y]) std::swap(x, y);
par[x] += par[y];
par[y] = x;
last[y] = t;
edge[x] += edge[y];
history[x].emplace_back(
t, par[x], edge[x],
std::max({std::get<3>(history[x].back()),
std::get<3>(history[y].back()), deg[memo1], deg[memo2]}));
return true;
}
bool is_ok(int t, int x, int y) {
x = root(t, x);
y = root(t, y);
if (x != y) return false;
auto Tuple = *prev(lower_bound(history[x].begin(), history[x].end(),
std::make_tuple(t, 0, 0, 0)));
if (-std::get<1>(Tuple) == std::get<2>(Tuple) or std::get<3>(Tuple) >= 3)
return true;
return false;
}
};
namespace cs_helper {
void zip_sort_renumber([[maybe_unused]] const std::vector<usize>& order) {}
template <class T, class... Args>
void zip_sort_renumber(const std::vector<usize>& order, std::vector<T>& head,
Args&... args) {
usize n = order.size();
assert(n == head.size());
std::vector<T> sorted_head(n);
for (usize i = 0; i < n; ++i) sorted_head[i] = head[order[i]];
head = std::move(sorted_head);
zip_sort_renumber(order, args...);
}
} // namespace cs_helper
template <class T, class... Args>
std::vector<usize> zip_sort(std::vector<T>& head, Args&... args) {
usize n = head.size();
std::vector<std::pair<T, usize>> tmp(n);
for (usize i = 0; i < n; ++i) tmp[i] = std::make_pair(head[i], i);
std::sort(tmp.begin(), tmp.end());
std::vector<usize> order(n);
for (usize i = 0; i < n; ++i) order[i] = tmp[i].second;
cs_helper::zip_sort_renumber(order, head, args...);
return order;
}
partially_persistent_UnionFind uf;
int N, M;
std::vector<int> U, V, W;
void init(int n_, int m_, std::vector<int> u_, std::vector<int> v_,
std::vector<int> w_) {
std::swap(N, n_);
std::swap(M, m_);
std::swap(U, u_);
std::swap(V, v_);
std::swap(W, w_);
zip_sort(W, U, V);
uf = partially_persistent_UnionFind(N);
for (usize i : range(0, M)) {
uf.merge(i, U[i], V[i]);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int ok = M, ng = -1;
while (ok - ng > 1) {
const int mid = (ok + ng) >> 1;
if (uf.is_ok(mid, X, Y))
ok = mid;
else
ng = mid;
}
return ok == M ? -1 : W[ok];
//
}
#ifdef CYN_LOCAL_INCLUDED
int main() {
int n = 5, m = 6;
std::vector<int> u = {0, 0, 1, 1, 1, 2};
std::vector<int> v = {1, 2, 2, 3, 4, 3};
std::vector<int> w = {4, 4, 1, 2, 10, 3};
init(n, m, u, v, w);
std::cout << getMinimumFuelCapacity(1, 2) << '\n';
}
#endif
