結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-21 15:39:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 62,086 bytes |
コンパイル時間 | 3,340 ms |
コンパイル使用メモリ | 273,400 KB |
最終ジャッジ日時 | 2025-01-16 04:00:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#line 1 "Library/yu2.cc"/** @file template.cpp* @brief Template*/#include <bits/extc++.h>#line 2 "Library/lib/alias"/** @file alias* @brief Alias*/#line 13 "Library/lib/alias"namespace workspace {constexpr char eol = '\n';using namespace std;using i32 = int_least32_t;using i64 = int_least64_t;using i128 = __int128_t;using u32 = uint_least32_t;using u64 = uint_least64_t;using u128 = __uint128_t;template <class T, class Comp = less<T>>using priority_queue = std::priority_queue<T, vector<T>, Comp>;template <class T> using stack = std::stack<T, vector<T>>;} // namespace workspace#line 2 "Library/lib/cxx20"/** @file cxx20* @brief C++20 Features*/#if __cplusplus <= 201703L#include <vector>namespace std {/** @fn erase_if* @brief Erase the elements of a container that do not satisfy the condition.* @param __cont Container.* @param __pred Predicate.* @return Number of the erased elements.*/template <typename _Tp, typename _Alloc, typename _Predicate>inline typename vector<_Tp, _Alloc>::size_type erase_if(vector<_Tp, _Alloc>& __cont, _Predicate __pred) {const auto __osz = __cont.size();__cont.erase(std::remove_if(__cont.begin(), __cont.end(), __pred),__cont.end());return __osz - __cont.size();}/** @fn erase* @brief Erase the elements of a container that are equal to the given value.* @param __cont Container.* @param __value Value.* @return Number of the erased elements.*/template <typename _Tp, typename _Alloc, typename _Up>inline typename vector<_Tp, _Alloc>::size_type erase(vector<_Tp, _Alloc>& __cont, const _Up& __value) {const auto __osz = __cont.size();__cont.erase(std::remove(__cont.begin(), __cont.end(), __value),__cont.end());return __osz - __cont.size();}} // namespace std#endif#line 2 "Library/lib/option"/** @file option* @brief Optimize Options*/#ifdef ONLINE_JUDGE#pragma GCC optimize("O3")#pragma GCC target("avx,avx2")#pragma GCC optimize("unroll-loops")#endif#line 2 "Library/src/utils/binary_search.hpp"/** @file binary_search.hpp* @brief Binary Search*/#if __cplusplus >= 201703L#include <cassert>#include <cmath>#include <vector>namespace workspace {/** @fn binary_search* @brief binary search on a discrete range.* @param ok pred(ok) is true* @param ng pred(ng) is false* @param pred the predicate* @return the closest point to (ng) where pred is true*/template <class iter_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, iter_type>, bool>,iter_type>binary_search(iter_type ok, iter_type ng, pred_type pred) {assert(ok != ng);std::make_signed_t<decltype(ng - ok)> dist(ng - ok);while (1 < dist || dist < -1) {iter_type mid(ok + dist / 2);if (pred(mid))ok = mid, dist -= dist / 2;elseng = mid, dist /= 2;}return ok;}/** @fn parallel_binary_search* @brief parallel binary search on discrete ranges.* @param ends a vector of pairs; pred(first) is true, pred(second) is false* @param pred the predicate* @return the closest points to (second) where pred is true*/template <class iter_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, std::vector<iter_type>>,std::vector<bool>>,std::vector<iter_type>>parallel_binary_search(std::vector<std::pair<iter_type, iter_type>> ends,pred_type pred) {std::vector<iter_type> mids(ends.size());for (;;) {bool all_found = true;for (size_t i{}; i != ends.size(); ++i) {auto [ok, ng] = ends[i];iter_type mid(ok + (ng - ok) / 2);if (mids[i] != mid) {all_found = false;mids[i] = mid;}}if (all_found) break;auto res = pred(mids);for (size_t i{}; i != ends.size(); ++i) {(res[i] ? ends[i].first : ends[i].second) = mids[i];}}return mids;}/** @fn binary_search* @brief binary search on the real number line.* @param ok pred(ok) is true* @param ng pred(ng) is false* @param eps the error tolerance* @param pred the predicate* @return the boundary point*/template <class real_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, real_type>, bool>,real_type>binary_search(real_type ok, real_type ng, const real_type eps, pred_type pred) {assert(ok != ng);for (auto loops = 0; loops != std::numeric_limits<real_type>::digits &&(ok + eps < ng || ng + eps < ok);++loops) {real_type mid{(ok + ng) / 2};(pred(mid) ? ok : ng) = mid;}return ok;}/** @fn parallel_binary_search* @brief parallel binary search on the real number line.* @param ends a vector of pairs; pred(first) is true, pred(second) is false* @param eps the error tolerance* @param pred the predicate* @return the boundary points*/template <class real_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, std::vector<real_type>>,std::vector<bool>>,std::vector<real_type>>parallel_binary_search(std::vector<std::pair<real_type, real_type>> ends,const real_type eps, pred_type pred) {std::vector<real_type> mids(ends.size());for (auto loops = 0; loops != std::numeric_limits<real_type>::digits;++loops) {bool all_found = true;for (size_t i{}; i != ends.size(); ++i) {auto [ok, ng] = ends[i];if (ok + eps < ng || ng + eps < ok) {all_found = false;mids[i] = (ok + ng) / 2;}}if (all_found) break;auto res = pred(mids);for (size_t i{}; i != ends.size(); ++i) {(res[i] ? ends[i].first : ends[i].second) = mids[i];}}return mids;}} // namespace workspace#endif#line 2 "Library/src/utils/chval.hpp"/** @file chval.hpp* @brief Change Less/Greater*/#line 9 "Library/src/utils/chval.hpp"namespace workspace {/** @fn chle* @brief Substitute y for x if comp(y, x) is true.* @param x Reference* @param y Const reference* @param comp Compare function* @return Whether or not x is updated*/template <class Tp, class Comp = std::less<Tp>>bool chle(Tp &x, const Tp &y, Comp comp = Comp()) {return comp(y, x) ? x = y, true : false;}/** @fn chge* @brief Substitute y for x if comp(x, y) is true.* @param x Reference* @param y Const reference* @param comp Compare function* @return Whether or not x is updated*/template <class Tp, class Comp = std::less<Tp>>bool chge(Tp &x, const Tp &y, Comp comp = Comp()) {return comp(x, y) ? x = y, true : false;}} // namespace workspace#line 2 "Library/src/utils/clock.hpp"/** @fn clock.hpp* @brief Clock*/#line 9 "Library/src/utils/clock.hpp"namespace workspace {using namespace std::chrono;namespace internal {// The start time of the program.const auto start_time{system_clock::now()};} // namespace internal/** @fn elapsed* @return elapsed time of the program*/int64_t elapsed() {const auto end_time{system_clock::now()};return duration_cast<milliseconds>(end_time - internal::start_time).count();}} // namespace workspace#line 5 "Library/src/utils/coordinate_compression.hpp"template <class T> class coordinate_compression {std::vector<T> uniquely;std::vector<size_t> compressed;public:coordinate_compression(const std::vector<T> &raw): uniquely(raw), compressed(raw.size()) {std::sort(uniquely.begin(), uniquely.end());uniquely.erase(std::unique(uniquely.begin(), uniquely.end()),uniquely.end());for (size_t i = 0; i != size(); ++i)compressed[i] =std::lower_bound(uniquely.begin(), uniquely.end(), raw[i]) -uniquely.begin();}size_t operator[](const size_t idx) const {assert(idx < size());return compressed[idx];}size_t size() const { return compressed.size(); }size_t count() const { return uniquely.size(); }T value(const size_t ord) const {assert(ord < count());return uniquely[ord];}size_t order(const T &value) const {return std::lower_bound(uniquely.begin(), uniquely.end(), value) -uniquely.begin();}auto begin() { return compressed.begin(); }auto end() { return compressed.end(); }auto rbegin() { return compressed.rbegin(); }auto rend() { return compressed.rend(); }};#line 2 "Library/src/utils/ejection.hpp"/** @file ejection.hpp* @brief Ejection*/#line 9 "Library/src/utils/ejection.hpp"namespace workspace {/** @brief eject from a try block, throw nullptr* @param arg output*/template <class Tp> void eject(Tp const &arg) {std::cout << arg << "\n";throw nullptr;}} // namespace workspace#line 2 "Library/src/utils/fixed_point.hpp"/** @file fixed_point.hpp* @brief Fixed Point Combinator*/#line 9 "Library/src/utils/fixed_point.hpp"namespace workspace {/** @class fixed_point* @brief Recursive calling of lambda expression.*/template <class lambda_type> class fixed_point {lambda_type func;public:/** @param func 1st arg callable with the rest of args, and the return type* specified.*/fixed_point(lambda_type &&func) : func(std::move(func)) {}/** @brief Recursively apply *this to 1st arg of func.* @param args Arguments of the recursive method.*/template <class... Args> auto operator()(Args &&... args) const {return func(*this, std::forward<Args>(args)...);}};} // namespace workspace#line 6 "Library/src/utils/hash.hpp"#line 2 "Library/src/utils/sfinae.hpp"/** @file sfinae.hpp* @brief SFINAE*/#line 10 "Library/src/utils/sfinae.hpp"#include <type_traits>template <typename T, class = void> struct is_complete : std::false_type {};template <typename T>struct is_complete<T, decltype(void(sizeof(T)))> : std::true_type {};template <class type, template <class> class trait>using enable_if_trait_type = typename std::enable_if<trait<type>::value>::type;template <class Container>using element_type = typename std::decay<decltype(*std::begin(std::declval<Container&>()))>::type;template <class T, class = int> struct mapped_of {using type = element_type<T>;};template <class T>struct mapped_of<T,typename std::pair<int, typename T::mapped_type>::first_type> {using type = typename T::mapped_type;};template <class T> using mapped_type = typename mapped_of<T>::type;template <class T, class = void> struct is_integral_ext : std::false_type {};template <class T>struct is_integral_ext<T, typename std::enable_if<std::is_integral<T>::value>::type>: std::true_type {};template <> struct is_integral_ext<__int128_t> : std::true_type {};template <> struct is_integral_ext<__uint128_t> : std::true_type {};#if __cplusplus >= 201402template <class T>constexpr static bool is_integral_ext_v = is_integral_ext<T>::value;#endiftemplate <typename T, typename = void> struct multiplicable_uint {using type = uint_least32_t;};template <typename T>struct multiplicable_uint<T, typename std::enable_if<(2 < sizeof(T))>::type> {using type = uint_least64_t;};template <typename T>struct multiplicable_uint<T, typename std::enable_if<(4 < sizeof(T))>::type> {using type = __uint128_t;};#line 8 "Library/src/utils/hash.hpp"namespace workspace {template <class T, class = void> struct hash : std::hash<T> {};#if __cplusplus >= 201703Ltemplate <class Unique_bits_type>struct hash<Unique_bits_type,enable_if_trait_type<Unique_bits_type,std::has_unique_object_representations>> {size_t operator()(uint64_t x) const {static const uint64_t m = std::random_device{}();x ^= x >> 23;x ^= m;x ^= x >> 47;return x - (x >> 32);}};#endiftemplate <class Key> size_t hash_combine(const size_t &seed, const Key &key) {return seed ^(hash<Key>()(key) + 0x9e3779b9 /* + (seed << 6) + (seed >> 2) */);}template <class T1, class T2> struct hash<std::pair<T1, T2>> {size_t operator()(const std::pair<T1, T2> &pair) const {return hash_combine(hash<T1>()(pair.first), pair.second);}};template <class... T> class hash<std::tuple<T...>> {template <class Tuple, size_t index = std::tuple_size<Tuple>::value - 1>struct tuple_hash {static uint64_t apply(const Tuple &t) {return hash_combine(tuple_hash<Tuple, index - 1>::apply(t),std::get<index>(t));}};template <class Tuple> struct tuple_hash<Tuple, size_t(-1)> {static uint64_t apply(const Tuple &t) { return 0; }};public:uint64_t operator()(const std::tuple<T...> &t) const {return tuple_hash<std::tuple<T...>>::apply(t);}};template <class hash_table> struct hash_table_wrapper : hash_table {using key_type = typename hash_table::key_type;size_t count(const key_type &key) const {return hash_table::find(key) != hash_table::end();}template <class... Args> auto emplace(Args &&... args) {return hash_table::insert(typename hash_table::value_type(args...));}};template <class Key, class Mapped = __gnu_pbds::null_type>using cc_hash_table =hash_table_wrapper<__gnu_pbds::cc_hash_table<Key, Mapped, hash<Key>>>;template <class Key, class Mapped = __gnu_pbds::null_type>using gp_hash_table =hash_table_wrapper<__gnu_pbds::gp_hash_table<Key, Mapped, hash<Key>>>;template <class Key, class Mapped>using unordered_map = std::unordered_map<Key, Mapped, hash<Key>>;template <class Key> using unordered_set = std::unordered_set<Key, hash<Key>>;} // namespace workspace#line 2 "Library/src/utils/io/casefmt.hpp"/** @file castfmt* @brief Case Output Format*/#line 2 "Library/src/utils/iterate_case.hpp"/** @file iterate_case.hpp* @brief Iterate Testcases*/namespace workspace {namespace internal {// The 1-based index of the current testcase.unsigned caseid;} // namespace internalvoid main();unsigned case_number();/** @fn iterate_main* @brief Iterate main function.*/void iterate_main() {for (unsigned total = case_number(), &counter = (internal::caseid = 1);counter <= total; ++counter) {try {main();} catch (std::nullptr_t) {}}}} // namespace workspace#line 9 "Library/src/utils/io/casefmt.hpp"namespace workspace {/** @fn casefmt* @brief printf("Case #%u: ", internal::caseid)* @param os Reference to ostream* @return os*/std::ostream& casefmt(std::ostream& os) {return os << "Case #" << internal::caseid << ": ";}} // namespace workspace#line 3 "Library/src/utils/io/read.hpp"namespace workspace {namespace internal {struct cast_read {template <class T> operator T() const {T value;workspace::cin >> value;return value;}};} // namespace internal/** @fn read* @tparam Tp The type of input.* @brief Read from stdin.*/template <class Tp = void> auto read() {typename std::remove_const<Tp>::type value;cin >> value;return value;}/** @fn read* @brief Read from stdin on type casting.*/template <> auto read<void>() { return internal::cast_read(); }} // namespace workspace#line 2 "Library/src/utils/io/setup.hpp"/** @file setup.hpp* @brief I/O Setup*/#line 10 "Library/src/utils/io/setup.hpp"namespace workspace {/** @fn io_setup* @brief Setup I/O before main process.*/__attribute__((constructor)) void io_setup() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(15);#ifdef _buffer_checkatexit([] {char bufc;if (std::cin >> bufc)std::cerr << "\n\033[43m\033[30mwarning: buffer not empty.\033[0m\n\n";});#endif}} // namespace workspace#line 2 "Library/src/utils/io/stream.hpp"/** @file stream.hpp* @brief Stream*/#include <cxxabi.h>#line 13 "Library/src/utils/io/stream.hpp"namespace workspace {/** @class istream* @brief A wrapper class for std::istream.*/class istream : std::istream {template <class Tp, typename = std::nullptr_t> struct helper {helper(std::istream &is, Tp &x) {for (auto &&e : x) helper<decltype(e)>(is, e);}};template <class Tp>struct helper<Tp,decltype(std::declval<std::decay<decltype(std::declval<std::istream &>() >> std::declval<Tp &>())>>(),nullptr)> {helper(std::istream &is, Tp &x) { is >> x; }};template <class T1, class T2> struct helper<std::pair<T1, T2>> {helper(std::istream &is, std::pair<T1, T2> &x) {helper<T1>(is, x.first), helper<T2>(is, x.second);}};template <class... Tps> struct helper<std::tuple<Tps...>> {helper(std::istream &is, std::tuple<Tps...> &x) { iterate(is, x); }private:template <class Tp, size_t N = 0> void iterate(std::istream &is, Tp &x) {if constexpr (N == std::tuple_size<Tp>::value)return;elsehelper<typename std::tuple_element<N, Tp>::type>(is, std::get<N>(x)),iterate<Tp, N + 1>(is, x);}};public:template <typename Tp> istream &operator>>(Tp &x) {helper<Tp>(*this, x);if (std::istream::fail()) {static auto once = atexit([] {std::cerr << "\n\033[43m\033[30mwarning: failed to read \'"<< abi::__cxa_demangle(typeid(Tp).name(), 0, 0, 0)<< "\'.\033[0m\n\n";});assert(!once);}return *this;}};namespace internal {auto *const cin_ptr = (istream *)&std::cin;}auto &cin = *internal::cin_ptr;// operator<< overloadstemplate <class T, class U>std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {return os << p.first << ' ' << p.second;}template <class tuple_t, size_t index> struct tuple_os {static std::ostream &apply(std::ostream &os, const tuple_t &t) {tuple_os<tuple_t, index - 1>::apply(os, t);return os << ' ' << std::get<index>(t);}};template <class tuple_t> struct tuple_os<tuple_t, 0> {static std::ostream &apply(std::ostream &os, const tuple_t &t) {return os << std::get<0>(t);}};template <class tuple_t> struct tuple_os<tuple_t, SIZE_MAX> {static std::ostream &apply(std::ostream &os, const tuple_t &t) { return os; }};template <class... T>std::ostream &operator<<(std::ostream &os, const std::tuple<T...> &t) {return tuple_os<std::tuple<T...>,std::tuple_size<std::tuple<T...>>::value - 1>::apply(os, t);}template <class Container,typename = decltype(std::begin(std::declval<Container>()))>typename std::enable_if<!std::is_same<typename std::decay<Container>::type, std::string>::value &&!std::is_same<typename std::decay<Container>::type, char *>::value,std::ostream &>::typeoperator<<(std::ostream &os, const Container &cont) {bool head = true;for (auto &&e : cont) head ? head = 0 : (os << ' ', 0), os << e;return os;}} // namespace workspace#line 2 "Library/src/utils/make_vector.hpp"/** @file make_vector.hpp* @brief Multi-dimensional Vector*/#if __cplusplus >= 201703L#include <tuple>#include <vector>namespace workspace {/** @brief Make a multi-dimensional vector.* @tparam Tp type of the elements* @tparam N dimension* @tparam S integer type* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N, typename S>constexpr auto make_vector(S* sizes, Tp const& init = Tp()) {static_assert(std::is_convertible_v<S, size_t>);if constexpr (N)return std::vector(*sizes,make_vector<Tp, N - 1, S>(std::next(sizes), init));elsereturn init;}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N, typename S>constexpr auto make_vector(const S (&sizes)[N], Tp const& init = Tp()) {return make_vector<Tp, N, S>((S*)sizes, init);}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N, typename S, size_t I = 0>constexpr auto make_vector(std::array<S, N> const& sizes,Tp const& init = Tp()) {static_assert(std::is_convertible_v<S, size_t>);if constexpr (I == N)return init;elsereturn std::vector(sizes[I], make_vector<Tp, N, S, I + 1>(sizes, init));}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N = SIZE_MAX, size_t I = 0, class... Args>constexpr auto make_vector(std::tuple<Args...> const& sizes,Tp const& init = Tp()) {using tuple_type = std::tuple<Args...>;if constexpr (I == std::tuple_size_v<tuple_type> || I == N)return init;else {static_assert(std::is_convertible_v<std::tuple_element_t<I, tuple_type>, size_t>);return std::vector(std::get<I>(sizes),make_vector<Tp, N, I + 1>(sizes, init));}}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, class Fst, class Snd>constexpr auto make_vector(std::pair<Fst, Snd> const& sizes,Tp const& init = Tp()) {static_assert(std::is_convertible_v<Fst, size_t>);static_assert(std::is_convertible_v<Snd, size_t>);return make_vector({(size_t)sizes.first, (size_t)sizes.second}, init);}} // namespace workspace#endif#line 3 "Library/src/utils/random_number_generator.hpp"template <typename num_type> class random_number_generator {typename std::conditional<std::is_integral<num_type>::value,std::uniform_int_distribution<num_type>,std::uniform_real_distribution<num_type>>::typeunif;std::mt19937 engine;public:random_number_generator(num_type min = std::numeric_limits<num_type>::min(),num_type max = std::numeric_limits<num_type>::max()): unif(min, max), engine(std::random_device{}()) {}num_type min() const { return unif.min(); }num_type max() const { return unif.max(); }// generate a random number in [min(), max()].num_type operator()() { return unif(engine); }};#line 2 "Library/src/utils/round_div.hpp"/** @file round_div.hpp* @brief Round Integer Division*/#line 9 "Library/src/utils/round_div.hpp"#line 11 "Library/src/utils/round_div.hpp"namespace workspace {/** @fn floor_div* @brief floor of fraction.* @param x the numerator* @param y the denominator* @return maximum integer z s.t. z <= x / y* @note y must be nonzero.*/template <typename T1, typename T2>constexpr typename std::enable_if<(is_integral_ext<T1>::value &&is_integral_ext<T2>::value),typename std::common_type<T1, T2>::type>::typefloor_div(T1 x, T2 y) {assert(y != 0);if (y < 0) x = -x, y = -y;return x < 0 ? (x - y + 1) / y : x / y;}/** @fn ceil_div* @brief ceil of fraction.* @param x the numerator* @param y the denominator* @return minimum integer z s.t. z >= x / y* @note y must be nonzero.*/template <typename T1, typename T2>constexpr typename std::enable_if<(is_integral_ext<T1>::value &&is_integral_ext<T2>::value),typename std::common_type<T1, T2>::type>::typeceil_div(T1 x, T2 y) {assert(y != 0);if (y < 0) x = -x, y = -y;return x < 0 ? x / y : (x + y - 1) / y;}} // namespace workspace#line 4 "Library/src/utils/trinary_search.hpp"// trinary search on discrete range.template <class iter_type, class comp_type>iter_type trinary(iter_type first, iter_type last, comp_type comp){assert(first < last);intmax_t dist(last - first);while(dist > 2){iter_type left(first + dist / 3), right(first + dist * 2 / 3);if(comp(left, right)) last = right, dist = dist * 2 / 3;else first = left, dist -= dist / 3;}if(dist > 1 && comp(first + 1, first)) ++first;return first;}// trinary search on real numbers.template <class comp_type>long double trinary(long double first, long double last, const long double eps, comp_type comp){assert(first < last);while(last - first > eps){long double left{(first * 2 + last) / 3}, right{(first + last * 2) / 3};if(comp(left, right)) last = right;else first = left;}return first;}#line 2 "Library/src/utils/wrapper.hpp"template <class Container> class reversed {Container &ref, copy;public:constexpr reversed(Container &ref) : ref(ref) {}constexpr reversed(Container &&ref = Container()) : ref(copy), copy(ref) {}constexpr auto begin() const { return ref.rbegin(); }constexpr auto end() const { return ref.rend(); }constexpr operator Container() const { return ref; }};#line 12 "Library/yu2.cc"int main() { workspace::iterate_main(); }unsigned workspace::case_number() {// return -1; // unspecified// int t; std::cin >> t; std::cin.ignore(); return t; // givenreturn 1;}#line 1 "Library/src/data_structure/Additional_union_find.hpp"// #line 2 "Additional_union_find.hpp"#ifndef Additional_union_find_hpp#define Additional_union_find_hpp#include <cassert>#include <functional>#include <vector>template <class T>class additional_union_find{size_t n;std::vector<int> link;T *const dat;const std::function<void(T&, T&)> merge;public:additional_union_find(const size_t _n, const std::function<void(T&, T&)> &f) : n(_n), link(n, -1), dat(new T[n]()), merge(f) {}additional_union_find(const size_t _n, const T &x, const std::function<void(T&, T&)> &f) : n(_n), link(n, -1), dat(new T[n](x)), merge(f) {}~additional_union_find() { delete[] dat; }size_t find(const size_t x) { assert(x < n); return link[x] < 0 ? x : (link[x] = find(link[x])); }size_t size() const { return n; }size_t size(const size_t x) { return -link[find(x)]; }bool same(const size_t x, const size_t y) { return find(x) == find(y); }bool unite(size_t x, size_t y){if((x = find(x)) == (y = find(y))) return false;if(link[x] > link[y]) std::swap(x, y);link[x] += link[y], link[y] = x;merge(dat[x], dat[y]);return true;}T &operator[](const size_t x) { return dat[find(x)]; }}; // class additional_union_find#endif#line 3 "Library/src/data_structure/convex_hull_trick/Li_Chao_tree.hpp"template <class T = long long, class Comp = std::less<T>, T infty = std::numeric_limits<T>::max()>class Li_Chao_tree{struct line{T slop = 0, icpt = infty;line *lch = nullptr, *rch = nullptr;~line() { delete lch; delete rch; }line *swap(line &rhs) { std::swap(slop, rhs.slop); std::swap(icpt, rhs.icpt); return this; }T eval(const T x) const { return slop * x + icpt; }}; // struct lineT lower, upper, eps;Comp comp;line *root = nullptr;// // insert a line for the interval [l, r).line *insert(line *const p, const T l, const T r, line ln){if(!p) return new line(ln);bool lcmp = comp(ln.eval(l), p->eval(l));bool rcmp = comp(ln.eval(r - eps), p->eval(r - eps));if(lcmp == rcmp) return lcmp ? p->swap(ln) : p;if(r - l <= eps) return p;T mid = (l + r) / 2;if(comp(ln.eval(mid), p->eval(mid))){p->swap(ln);lcmp = !lcmp;}if(lcmp) p->lch = insert(p->lch, l, mid, ln);else p->rch = insert(p->rch, mid, r, ln);return p;}// // insert a segment for the interval [l, r).line *insert(line *const p, const T l, const T r, line ln, const T s, const T t){if(t - eps < l || r - eps < s) return p;T mid = (l + r) / 2;if(l < s or t < r){line *np = p ? p : new line;np->lch = insert(np->lch, l, mid, ln, s, t);np->rch = insert(np->rch, mid, r, ln, s, t);return np;}if(!p) return new line(ln);bool lcmp = comp(ln.eval(l), p->eval(l));bool rcmp = comp(ln.eval(r - eps), p->eval(r - eps));if(lcmp == rcmp) return lcmp ? p->swap(ln) : p;if(r - l <= eps) return p;if(comp(ln.eval(mid), p->eval(mid))){p->swap(ln);lcmp = !lcmp;}if(lcmp) p->lch = insert(p->lch, l, mid, ln, s, t);else p->rch = insert(p->rch, mid, r, ln, s, t);return p;}public:// domain set to be the interval [lower, upper).Li_Chao_tree(const T lower, const T upper, const T eps = 1, Comp comp = Comp()): lower(lower), upper(upper), eps(eps), comp(comp) {}~Li_Chao_tree() { delete root; }bool empty() const { return !root; }// insert a line whose slope is p and inception is q.void insert(const T p, const T q) { root = insert(root, lower, upper, line{p, q}); }// insert a line(segment) whose slope is p, inception is q,// and domain is the interval [s, t).void insert(const T p, const T q, const T s, const T t) { if(s < t) root = insert(root, lower, upper, line{p, q}, s, t); }T get(const T x) const{line *p = root;T l = lower, r = upper;T res = infty;while(p){T nval = p->eval(x);if(comp(nval, res)) res = nval;if(r - l <= eps) return res;T mid = (l + r) / 2;if(x < mid){p = p->lch;r = mid;}else{p = p->rch;l = mid;}}return res;}}; // class Li_Chao_tree#line 4 "Library/src/data_structure/convex_hull_trick/monotone.hpp"template <class T> class lower_convex_monotone {struct line {T slop, icpt;T eval(const T x) const { return slop * x + icpt; }};std::vector<line> lines;typename std::vector<line>::iterator lp, rp;void realloc() {if (rp != lines.end()) return;std::vector<line> copy((rp - lp) * 2 + 1);copy.swap(lines);rp = copy(lp, rp, lines.begin());lp = lines.begin();}public:lower_convex_monotone() : lines(2), lp(lines.begin()), rp(lp) {}bool empty() const { return lp == rp; }void clear() { rp = lp = lines.begin(); }void add(const T a, const T b) {while (rp - lp > 1) {auto [a1, b1] = *(rp - 1);auto [a2, b2] = *(rp - 2);if ((b - b1) * (a2 - a) > (b - b2) * (a1 - a)) break;--rp;}if (rp == lp) rp = lp = lines.begin();realloc();*rp++ = {a, b};}T get(const T x) {assert(!empty());while (rp - lp > 1 && lp->eval(x) > (lp + 1)->eval(x)) ++lp;return lp->eval(x);}}; // class lower_convex_monotone#line 4 "Library/src/data_structure/deque_aggregation.hpp"// implementation with dynamic memory allocation.template <class monoid>class deque_aggregation{template <bool left_operand_added>class stack_aggregation{friend deque_aggregation;struct data { monoid value, acc; };size_t capacity;data *stack, *end, *itr;bool top_referred;void recalc(){if(top_referred){assert(itr != stack);top_referred = false;monoid top_val{top().value};pop();push(top_val);}}public:stack_aggregation() : capacity(1), stack(new data[1]), end(std::next(stack)), itr(stack), top_referred() {}~stack_aggregation() { delete[] stack; }bool empty() const { return stack == itr; }size_t size() const { return itr - stack; }// copy of the element at the index.data operator[](size_t index) const{assert(index < size());recalc();return stack[index];}// reference to the last elementdata &top(){assert(itr != stack);top_referred = true;return *std::prev(itr);}void pop(){assert(itr != stack);--itr;top_referred = false;}void push(const monoid &mono){recalc();if(itr == end){data *tmp = new data[capacity << 1];std::swap(stack, tmp);end = (itr = std::copy(tmp, tmp + capacity, stack)) + capacity;capacity <<= 1;delete[] tmp;}if(left_operand_added) *itr = data{mono, mono + fold()};else *itr = data{mono, fold() + mono};++itr;}monoid fold(){if(itr == stack) return monoid();recalc();return std::prev(itr)->acc;}}; // class stack_aggregationstack_aggregation<true> left;stack_aggregation<false> right;void balance_to_left(){if(!left.empty() || right.empty()) return;left.recalc(); right.recalc();size_t mid = (right.size() + 1) >> 1;auto *itr = right.stack + mid;do { left.push((--itr)->value); } while(itr != right.stack);monoid acc;for(auto *p = right.stack + mid; p != right.itr; ++p, ++itr){*itr = {p->value, acc = acc + p->value};}right.itr = itr;}void balance_to_right(){if(!right.empty() || left.empty()) return;left.recalc(); right.recalc();size_t mid = (left.size() + 1) >> 1;auto *itr = left.stack + mid;do { right.push((--itr)->value); } while(itr != left.stack);monoid acc;for(auto *p = left.stack + mid; p != left.itr; ++p, ++itr){*itr = {p->value, acc = p->value + acc};}left.itr = itr;}public:bool empty() const { return left.empty() && right.empty(); }size_t size() const { return left.size() + right.size(); }// reference to the first element.monoid &front() { assert(!empty()); balance_to_left(); return left.top().value; }// reference to the last element.monoid &back() { assert(!empty()); balance_to_right(); return right.top().value; }// copy of the element at the index.monoid operator[](size_t index) const{assert(index < left.size() + right.size());return index < left.size() ? left[index].value : right[index - left.size()].value;}void push_front(const monoid &mono) { left.push(mono); }void push_back(const monoid &mono) { right.push(mono); }void pop_front(){assert(!empty());balance_to_left();left.pop();}void pop_back(){assert(!empty());balance_to_right();right.pop();}monoid fold() { return left.fold() + right.fold(); }}; // class deque_aggregation#line 2 "Library/src/data_structure/Mo.hpp"/** @file Mo.hpp* @brief Mo's Algorithm*/#line 13 "Library/src/data_structure/Mo.hpp"namespace workspace {/** @class Mo* @brief process queries about contiguous subarray* @tparam Push_back* @tparam Pop_back* @tparam Push_front Push_back as default* @tparam Pop_front Pop_back as default*/template <class Push_back, class Pop_back, class Push_front = Push_back,class Pop_front = Pop_back>class Mo {Push_front push_front;Pop_front pop_front;Push_back push_back;Pop_back pop_back;std::vector<size_t> lft, rgt, ord;std::vector<size_t>::iterator itr;size_t lpos, rpos;public:/** @param push_back* @param pop_back*/Mo(Push_back push_back, Pop_back pop_back): Mo(push_back, pop_back, push_back, pop_back) {}/** @param push_front* @param pop_front* @param push_back* @param pop_back*/Mo(Push_front push_front, Pop_front pop_front, Push_back push_back,Pop_back pop_back): push_front(push_front),pop_front(pop_front),push_back(push_back),pop_back(pop_back),lpos(),rpos() {}/** @return number of queries*/size_t size() const { return lft.size(); }/** @brief add query* @param l left end, inclusive* @param r right end, exclusive*/void set(size_t l, size_t r) {assert(!(r < l));lft.emplace_back(l), rgt.emplace_back(r);}/** @brief sort queries*/void make() {assert(size());ord.resize(size());iota(ord.begin(), ord.end(), 0);const size_t width = sqrt(*max_element(rgt.begin(), rgt.end()));std::sort(ord.begin(), ord.end(), [&](size_t x, size_t y) {if (lft[x] / width != lft[y] / width) return lft[x] < lft[y];return rgt[x] < rgt[y];});itr = ord.begin();}/** @brief process one query* @return index of query*/size_t process() {if (itr == ord.end()) return ord.size();const size_t id = *itr++, l = lft[id], r = rgt[id];while (lpos > l) push_front(--lpos);while (rpos < r) push_back(rpos++);while (lpos < l) pop_front(lpos++);while (rpos > r) pop_back(--rpos);return id;}};} // namespace workspace#line 5 "Library/src/data_structure/segment_tree/basic.hpp"#line 2 "Library/algebra/system/monoid.hpp"/** @file monoid.hpp* @brief Monoid*/#line 9 "Library/algebra/system/monoid.hpp"namespace workspace {template <class T, class E = T> struct min_monoid {using value_type = T;static T min, max;T value;min_monoid() : value(max) {}min_monoid(const T &value) : value(value) {}operator T() const { return value; }min_monoid operator+(const min_monoid &rhs) const {return value < rhs.value ? *this : rhs;}min_monoid operator*(const E &rhs) const;};template <class T, class E>T min_monoid<T, E>::min = std::numeric_limits<T>::min() / 2;template <class T, class E>T min_monoid<T, E>::max = std::numeric_limits<T>::max() / 2;template <class T, class E = T> struct max_monoid : min_monoid<T, E> {using base = min_monoid<T, E>;using base::min_monoid;max_monoid() : base(base::min) {}max_monoid operator+(const max_monoid &rhs) const {return !(base::value < rhs.value) ? *this : rhs;}max_monoid operator*(const E &rhs) const;};} // namespace workspace#line 3 "Library/src/data_structure/segment_tree/waitlist.hpp"namespace internal {struct waitlist : std::queue<size_t> {waitlist(size_t n) : in(n) {}bool push(size_t index) {assert(index < in.size());if (in[index]) return false;emplace(index);return (in[index] = true);}size_t pop() {assert(!empty());auto index = front();std::queue<size_t>::pop();in[index] = false;return index;}private:std::vector<int_least8_t> in;};}#line 9 "Library/src/data_structure/segment_tree/basic.hpp"template <class Monoid, class Container = std::vector<Monoid>>class segment_tree {static_assert(std::is_same<Monoid, mapped_type<Container>>::value);size_t size_orig, height, size_ext;Container data;internal::waitlist wait;void repair() {while (!wait.empty()) {const size_t index = wait.pop() >> 1;if (index && wait.push(index)) pull(index);}}void pull(const size_t node) {data[node] = data[node << 1] + data[node << 1 | 1];}template <class Pred>size_t left_partition_subtree(size_t index, const Pred pred,Monoid mono) const {assert(index);while (index < size_ext) {const Monoid tmp = data[(index <<= 1) | 1] + mono;if (pred(tmp))mono = tmp;else++index;}return ++index -= size_ext;}template <class Pred>size_t right_partition_subtree(size_t index, const Pred pred,Monoid mono) const {assert(index);while (index < size_ext) {const Monoid tmp = mono + data[index <<= 1];if (pred(tmp)) ++index, mono = tmp;}return (index -= size_ext) < size_orig ? index : size_orig;}public:using value_type = Monoid;segment_tree(const size_t n = 0): size_orig{n},height(n > 1 ? 32 - __builtin_clz(n - 1) : 0),size_ext{1u << height},data(size_ext << 1),wait(size_ext << 1) {}segment_tree(const size_t n, const Monoid &init) : segment_tree(n) {std::fill(std::next(std::begin(data), size_ext), std::end(data), init);for (size_t i{size_ext}; --i;) pull(i);}template <class iter_type, class value_type = typename std::iterator_traits<iter_type>::value_type>segment_tree(iter_type first, iter_type last): size_orig(std::distance(first, last)),height(size_orig > 1 ? 32 - __builtin_clz(size_orig - 1) : 0),size_ext{1u << height},data(size_ext << 1),wait(size_ext << 1) {static_assert(std::is_constructible<Monoid, value_type>::value,"Monoid(iter_type::value_type) is not constructible.");for (auto iter{std::next(std::begin(data), size_ext)};iter != std::end(data) && first != last; ++iter, ++first)*iter = Monoid{*first};for (size_t i{size_ext}; --i;) pull(i);}template <class Cont, typename = typename Cont::value_type>segment_tree(const Cont &cont): segment_tree(std::begin(cont), std::end(cont)) {}size_t size() const { return size_orig; }size_t capacity() const { return size_ext; }// reference to the element at the index.Monoid &operator[](size_t index) {assert(index < size_orig);wait.push(index |= size_ext);return data[index];}// const reference to the element at the index.const Monoid &operator[](size_t index) const {assert(index < size_orig);return data[index |= size_orig];}Monoid fold(size_t first, size_t last) {assert(last <= size_orig);repair();Monoid leftval{}, rightval{};first += size_ext, last += size_ext;while (first < last) {if (first & 1) leftval = leftval + data[first++];if (last & 1) rightval = data[--last] + rightval;first >>= 1, last >>= 1;}return leftval + rightval;}Monoid fold() { return fold(0, size_orig); }template <class Pred> size_t left_partition(size_t right, Pred pred) {assert(right <= size_orig);repair();right += size_ext;Monoid mono{};for (size_t left{size_ext}; left != right; left >>= 1, right >>= 1) {if ((left & 1) != (right & 1)) {const Monoid tmp = data[--right] + mono;if (!pred(tmp)) return left_partition_subtree(right, pred, mono);mono = tmp;}}return 0;}template <class Pred> size_t right_partition(size_t left, Pred pred) {assert(left <= size_orig);repair();left += size_ext;Monoid mono{};for (size_t right{size_ext << 1}; left != right; left >>= 1, right >>= 1) {if ((left & 1) != (right & 1)) {const Monoid tmp = mono + data[left];if (!pred(tmp)) return right_partition_subtree(left, pred, mono);mono = tmp;++left;}}return size_orig;}}; // class segment_tree#line 5 "Library/src/data_structure/segment_tree/lazy.hpp"#line 9 "Library/src/data_structure/segment_tree/lazy.hpp"template <class Monoid, class Endomorphism,class Monoid_container = std::vector<Monoid>,class Endomorphism_container = std::vector<Endomorphism>>class lazy_segment_tree {static_assert(std::is_same<Monoid, mapped_type<Monoid_container>>::value);static_assert(std::is_same<Endomorphism, mapped_type<Endomorphism_container>>::value);static_assert(std::is_same<Monoid, decltype(Monoid{} + Monoid{})>::value,"\'Monoid\' has no proper binary operator+.");static_assert(std::is_same<Endomorphism,decltype(Endomorphism{} * Endomorphism{})>::value,"\'Endomorphism\' has no proper binary operator*.");static_assert(std::is_same<Monoid, decltype(Monoid{} * Endomorphism{})>::value,"\'Endomorphism\' is not applicable to \'Monoid\'.");size_t size_orig, height, size_ext;Monoid_container data;Endomorphism_container lazy;internal::waitlist wait;void repair() {while (!wait.empty()) {const size_t index = wait.pop() >> 1;if (index && wait.push(index)) pull(index);}}void apply(size_t node, const Endomorphism &endo) {data[node] = data[node] * endo;if (node < size_ext) lazy[node] = lazy[node] * endo;}void push(size_t node) {if (!(node < size_ext)) return;apply(node << 1, lazy[node]);apply(node << 1 | 1, lazy[node]);lazy[node] = Endomorphism{};}void pull(size_t node) { data[node] = data[node << 1] + data[node << 1 | 1]; }template <class Pred>size_t left_partition_subtree(size_t node, Pred pred, Monoid mono) {assert(node);while (node < size_ext) {push(node);const Monoid &tmp = data[(node <<= 1) | 1] + mono;if (pred(tmp))mono = tmp;else++node;}return ++node -= size_ext;}template <class Pred>size_t right_partition_subtree(size_t node, Pred pred, Monoid mono) {assert(node);while (node < size_ext) {push(node);const Monoid &tmp = mono + data[node <<= 1];if (pred(tmp)) ++node, mono = tmp;}return (node -= size_ext) < size_orig ? node : size_orig;}public:using value_type = Monoid;lazy_segment_tree(size_t n = 0): size_orig{n},height(n > 1 ? 32 - __builtin_clz(n - 1) : 0),size_ext{1u << height},data(size_ext << 1),lazy(size_ext),wait(size_ext << 1) {}lazy_segment_tree(size_t n, const Monoid &init) : lazy_segment_tree(n) {std::fill(std::next(std::begin(data), size_ext), std::end(data), init);for (size_t i{size_ext}; --i;) pull(i);}template <class iter_type, class value_type = typename std::iterator_traits<iter_type>::value_type>lazy_segment_tree(iter_type first, iter_type last): size_orig(std::distance(first, last)),height(size_orig > 1 ? 32 - __builtin_clz(size_orig - 1) : 0),size_ext{1u << height},data(size_ext << 1),lazy(size_ext),wait(size_ext << 1) {static_assert(std::is_constructible<Monoid, value_type>::value,"Monoid(iter_type::value_type) is not constructible.");for (auto iter{std::next(std::begin(data), size_ext)};iter != std::end(data) && first != last; ++iter, ++first)*iter = Monoid(*first);for (size_t i{size_ext}; --i;) pull(i);}template <class Container, typename = element_type<Container>>lazy_segment_tree(const Container &cont): lazy_segment_tree(std::begin(cont), std::end(cont)) {}size_t size() const { return size_orig; }size_t capacity() const { return size_ext; }Monoid &operator[](size_t index) {assert(index < size_orig);index |= size_ext;wait.push(index);for (size_t i = height; i; --i) push(index >> i);return data[index];}void update(size_t index, const Endomorphism &endo) {update(index, index + 1, endo);}void update(size_t first, size_t last, const Endomorphism &endo) {assert(last <= size_orig);repair();if (first >= last) return;first += size_ext, last += size_ext - 1;for (size_t i = height; i; --i) push(first >> i), push(last >> i);for (size_t l = first, r = last + 1; last; l >>= 1, r >>= 1) {if (l < r) {if (l & 1) apply(l++, endo);if (r & 1) apply(--r, endo);}if (first >>= 1, last >>= 1) {pull(first), pull(last);}}}Monoid fold() { return fold(0, size_orig); }Monoid fold(size_t first, size_t last) {assert(last <= size_orig);repair();if (first >= last) return Monoid{};first += size_ext, last += size_ext - 1;Monoid left_val{}, right_val{};for (size_t l = first, r = last + 1; last; l >>= 1, r >>= 1) {if (l < r) {if (l & 1) left_val = left_val + data[l++];if (r & 1) right_val = data[--r] + right_val;}if (first >>= 1, last >>= 1) {left_val = left_val * lazy[first];right_val = right_val * lazy[last];}}return left_val + right_val;}template <class Pred> size_t left_partition(size_t right, Pred pred) {assert(right <= size_orig);repair();right += size_ext - 1;for (size_t i{height}; i; --i) push(right >> i);++right;Monoid mono{};for (size_t left{size_ext}; left != right; left >>= 1, right >>= 1) {if ((left & 1) != (right & 1)) {const Monoid &tmp = data[--right] + mono;if (!pred(tmp)) return left_partition_subtree(right, pred, mono);mono = tmp;}}return 0;}template <class Pred> size_t right_partition(size_t left, Pred pred) {assert(left <= size_orig);repair();left += size_ext;for (size_t i{height}; i; --i) push(left >> i);Monoid mono{};for (size_t right{size_ext << 1}; left != right; left >>= 1, right >>= 1) {if ((left & 1) != (right & 1)) {const Monoid &tmp = mono + data[left];if (!pred(tmp)) return right_partition_subtree(left, pred, mono);mono = tmp;++left;}}return size_orig;}}; // class lazy_segment_tree#line 1 "Library/src/data_structure/Skew_heap.hpp"// #line 2 "Skew_heap.hpp"#ifndef Skew_heap_hpp#define Skew_heap_hpptemplate <class T>class skew_heap{const std::function<bool(const T&, const T&)> comp;public:struct node{node *lft, *rgt; T key;~node() { delete lft; delete rgt; }private:friend skew_heap;void clear() { lft = rgt = nullptr; }}; // struct nodeskew_heap(const std::function<bool(const T&, const T&)> &f = std::less<T>()) : comp(f) {}node *make() const { return nullptr; }node *push(node *root, const T &key) const{return meld(root, new node{ nullptr, nullptr, key });}node* pop(node *root) const{node *nroot = meld(root->lft, root->rgt);return root->clear(), nroot;}node *meld(node *x, node *y) const{if(!x) return y;if(!y) return x;if(comp(x->key, y->key)) std::swap(x, y);x->rgt = meld(y, x->rgt);std::swap(x->lft, x->rgt);return x;}bool empty(node *root) const { return !root; }}; // class skew_heap#endif#line 2 "Library/src/data_structure/union_find/basic.hpp"/** @file basic.hpp* @brief Basic Union-Find*/#line 11 "Library/src/data_structure/union_find/basic.hpp"namespace workspace {template <typename Tp> struct union_find {protected:using signed_t = typename std::make_signed<Tp>::type;using unsigned_t = typename std::make_unsigned<Tp>::type;std::vector<signed_t> link;public:/** @param n The number of nodes.*/union_find(Tp n = 0) : link(n, 1) {}/** @fn find* @param x A node.* @return The representative of the group.*/virtual unsigned_t find(unsigned_t x) {assert(x < size());return link[x] > 0 ? x : -(link[x] = -(signed_t)find(-link[x]));}/** @fn size* @return The number of nodes.*/unsigned_t size() const { return link.size(); }/** @fn size* @param x A node.* @return The number of nodes in the group.*/virtual unsigned_t size(unsigned_t x) {assert(x < size());return link[find(x)];}/** @fn same* @param x 1st node.* @param y 2nd node.* @return Whether or not the two nodes belong to the same group.*/bool same(unsigned_t x, unsigned_t y) {assert(x < size());assert(y < size());return find(x) == find(y);}/** @fn unite* @param x 1st node.* @param y 2nd node.* @return Whether or not the two groups were merged anew.*/virtual bool unite(unsigned_t x, unsigned_t y) {assert(x < size()), x = find(x);assert(y < size()), y = find(y);if (x == y) return false;if (link[x] < link[y]) std::swap(x, y);link[x] += link[y];link[y] = -(signed_t)x;return true;}};} // namespace workspace#line 2 "Library/src/data_structure/union_find/bipartite.hpp"/** @file bipartite.hpp* @brief Bipartite Union-Find*/#line 9 "Library/src/data_structure/union_find/bipartite.hpp"namespace workspace {class bipartite_union_find : public union_find<uint_least64_t> {using base = union_find<uint_least64_t>;using base::union_find;constexpr static unsigned_t sgnb = unsigned_t(1) << 32, mask = sgnb - 1,ubs = ~unsigned_t(0) ^ mask;public:unsigned_t find(unsigned_t x) override {assert(x < base::size());if (link[x] > 0) return x;const auto p = -link[x] & mask, r = find(p);if (r != p) link[x] = -(link[x] ^ p ^ link[p]);return r;}bool diff(unsigned_t x) {assert(x < base::size()), find(x);return link[x] > 0 ? 0 : link[x] >> 32 & 1;}// bool diff(unsigned_t x, unsigned_t y) {}unsigned_t size(size_t x, bool neq) {assert(x < base::size()), x = find(x);return neq ? link[x] >> 32 : link[x] & mask;}unsigned_t size(size_t x) override {assert(x < base::size()), x = find(x);return (link[x] >> 32) + (link[x] & mask);}/** @fn unite* @param x 1st node.* @param y 2nd node.* @param flip* @return Whether or not the relation is consistent.*/bool unite(size_t x, size_t y, bool flip = true) {assert(x < base::size()), flip ^= diff(x), x = find(x);assert(y < base::size()), flip ^= diff(y), y = find(y);if (x == y) return !flip;if (link[x] < link[y]) std::swap(x, y);link[x] += flip ? (unsigned_t)link[y] << 32 | link[y] >> 32 : link[y];link[y] = flip ? (mask + 1) ^ -x : -x;return true;}};} // namespace workspace#line 1 "Library/src/data_structure/union_find/bipartite_union_find.hpp"// verified at https://codeforces.com/contest/1290/submission/70120095#ifndef bipartite_union_find_hpp#define bipartite_union_find_hpp#include <cassert>#include <utility>class bipartite_union_find{class node{node *link = nullptr;bool mark = 0;unsigned cnt[2] = {1, 0};public:unsigned size() const { return cnt[0] + cnt[1]; }unsigned size(const bool color) const { return cnt[color]; }node *find(){if(!link) return this;node *const root = link->find();mark ^= link->mark;return link = root;}bool color() { return find(), mark; }void merge(node *other, const bool flip){other->link = this, other->mark = flip;for(bool i : {0, 1}) cnt[i] += other->cnt[i ^ flip];}}; // class nodeunsigned n; node *tree;bool unite(node *x, node *y, bool diff_color){diff_color ^= x->color() ^ y->color();x = x->find(), y = y->find();if(x == y) return !diff_color;if(x->size() < y->size()) std::swap(x, y);x->merge(y, diff_color);return true;}public:bipartite_union_find() : n(), tree() {}explicit bipartite_union_find(const unsigned _n) : n(_n), tree(new node[_n]) {}~bipartite_union_find() { delete[] tree; }bool empty() const { return !tree; }unsigned find(const unsigned x){assert(x < n);return tree[x].find() - tree;}unsigned size() const { return n; }unsigned size(const unsigned x){assert(x < n);return tree[x].find()->size();}unsigned size(const unsigned x, const bool color){assert(x < n);return tree[x].find()->size(color);}bool color(const unsigned x){assert(x < n);return tree[x].color();}bool same(const unsigned x, const unsigned y){assert(x < n && y < n);return tree[x].find() == tree[y].find();}bool unite_same(unsigned x, unsigned y){assert(x < size()); assert(y < size());return unite(tree + x, tree + y, false);}bool unite_diff(unsigned x, unsigned y){assert(x < size()); assert(y < size());return unite(tree + x, tree + y, true);}}; // class bipartite_union_find#endif // bipartite_union_find_hpp#line 1 "Library/src/data_structure/union_find/partially_persistent_union_find.hpp"// #line 2 "Partially_persistent_union_find.hpp"// veryfied at https://atcoder.jp/contests/agc002/submissions/9514048#ifndef Partially_persistent_union_find_hpp#define Partially_persistent_union_find_hpp#include <cstdint>#include <cstddef>#include <numeric>#include <vector>class partially_persistent_union_find{using time_type = uint32_t;struct log_type { time_type time; size_t size; };const size_t n;std::vector<size_t> parent;std::vector<time_type> last;std::vector<std::vector<log_type>> size_log;time_type clock;public:explicit partially_persistent_union_find(size_t _n) : n(_n), parent(n), last(n, UINT32_MAX), size_log(n, std::vector<log_type>(1, {0, 1})),clock(){std::iota(parent.begin(), parent.end(), 0);}size_t size(size_t x, time_type t = UINT32_MAX){size_t root = find(x, t);auto __ok{size_log[root].begin()}, __ng{size_log[root].end()};auto dist = __ng - __ok;while(dist > 1){auto mid{__ok + (dist >> 1)};if(mid->time > t) __ng = mid, dist >>= 1;else __ok = mid, ++dist >>= 1;}return __ok->size;}size_t find(size_t x, size_t t = UINT32_MAX) { return last[x] >= t ? x : find(parent[x], t); }bool same(size_t x, size_t y, time_type t = UINT32_MAX) { return find(x, t) == find(y, t); }time_type unite(size_t x, size_t y){if((x = find(x)) != (y = find(y))){size_t size_x = size_log[x].back().size;size_t size_y = size_log[y].back().size;if(size_x < size_y) std::swap(x, y), std::swap(size_x, size_y);size_log[x].push_back({clock + 1, size_x + size_y});parent[y] = x;last[y] = clock;}return ++clock;}}; // class partially_persistent_union_find#endif#line 1 "Library/src/data_structure/union_find/potentialized_union_find.hpp"// #line 2 "potentialized_union_find.hpp"// verified at https://atcoder.jp/contests/abc087/submissions/9511701#ifndef Potentialized_union_find_hpp#define Potentialized_union_find_hpp#include <cassert>#include <cstddef>#include <vector>template <class Abelian>class potentialized_union_find{size_t n;std::vector<int> link;std::vector<Abelian> diff_weight;public:explicit potentialized_union_find(size_t _n) : n(_n), link(n, -1), diff_weight(n) {}size_t find(const size_t x){assert(x < n);if(link[x] < 0) return x;const size_t root = find(link[x]);diff_weight[x] += diff_weight[link[x]];return link[x] = root;}size_t size() const { return n; }size_t size(const size_t x) { return -link[find(x)]; }Abelian weight(size_t x) { return find(x), diff_weight[x]; }Abelian diff(size_t x, size_t y) { return weight(y) - weight(x); }bool same(const size_t x, const size_t y) { return find(x) == find(y); }bool unite(size_t x, size_t y, Abelian w){w += weight(x) - weight(y);x = find(x), y = find(y);if(x == y) return false;if(link[x] > link[y]) std::swap(x, y), w = -w;link[x] += link[y], link[y] = x;diff_weight[y] = w;return true;}}; // class potentialized_union_find#endif#line 2 "Library/src/data_structure/union_find/unbalanced.hpp"/** @file unbalanced.hpp* @brief Unbalanced Union-Find*/#line 9 "Library/src/data_structure/union_find/unbalanced.hpp"namespace workspace {class unbalanced_union_find : public union_find<uint_least32_t> {using base = union_find<uint_least32_t>;public:using base::union_find;bool unite(unsigned_t x, unsigned_t y) override {assert(x < size()), x = find(x);assert(y < size()), y = find(y);if (x == y) return false;link[x] += link[y];link[y] = -(signed_t)x;return true;}};} // namespace workspace#line 22 "Library/yu2.cc"namespace workspace {void main() {// start here!int n, d, w;cin >> n >> d >> w;union_find uf1(n), uf2(n);for (auto i = 0; i < d; ++i) {int a, b;cin >> a >> b;--a, --b;uf1.unite(a, b);}for (auto i = 0; i < w; ++i) {int a, b;cin >> a >> b;--a, --b;uf2.unite(a, b);}vector<set<int>> go(n);for (auto i = 0; i < n; ++i) {go[uf1.find(i)].emplace(uf2.find(i));}i64 ans = 0;for (auto i = 0; i < n; ++i) {i64 sum = 0;for (auto &&r : go[i]) {sum += uf2.size(r);}ans += sum * uf1.size(i);}cout << ans - n << eol;}} // namespace workspace