結果
問題 | No.2252 Find Zero |
ユーザー | mind_cpp |
提出日時 | 2023-03-25 04:35:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 55,648 bytes |
コンパイル時間 | 5,728 ms |
コンパイル使用メモリ | 332,000 KB |
実行使用メモリ | 25,836 KB |
平均クエリ数 | 2.00 |
最終ジャッジ日時 | 2024-09-18 17:57:05 |
合計ジャッジ時間 | 7,704 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 45 ms
24,800 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 51 ms
25,052 KB |
testcase_11 | AC | 49 ms
25,324 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 44 ms
24,940 KB |
testcase_15 | WA | - |
testcase_16 | AC | 47 ms
24,556 KB |
testcase_17 | WA | - |
ソースコード
#ifdef INCLUDED_MAIN// const ll ansmod = 998244353;// const ll ansmod = 1000000007;auto solve() {GET(N);rep(i, 0, N, 2) {string s = "? " + STR(i) + " " + STR(i + 1);printF(s);GET(ans);if (ans == i) {string outstr = "! " + STR(i + 1);printF(outstr);return _0;} else {string outstr = "! " + STR(i);printF(outstr);return _0;}}string outstr = "! " + STR(N - 1);printF(outstr);return _0;}int main() {auto ans = solve();// auto ans = (ansmod + (solve() % ansmod)) % ansmod;// print(ans);}// ラムダ再帰// auto ff = [&](auto &&f, ll x) {};// ff(ff, 0);// 以下は動作確認未実施#else#define INCLUDED_MAIN#ifdef LOCAL#include "../mytemplate.hpp"#else#include <algorithm>#include <bits/extc++.h>#include <bitset>#include <cassert>#include <cctype>#include <climits>#include <cstddef>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <map>#include <queue>#include <random>#include <set>#include <stack>#include <string_view>#include <type_traits>#include <utility>#include <regex>#endifusing namespace std;// clang-format off/* accelration */// 高速バイナリ生成#ifndef LOCAL#pragma GCC target("avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#endif/* alias */using ull = __uint128_t;// using ll = long long; // __int128でTLEするときに切り替える。using ll = __int128;using ld = long double;using vi = vector<int>;using vl = vector<long>;using vll = vector<ll>;using vd = vector<ld>;using vvi = vector<vi>;using vvl = vector<vl>;using vvll = vector<vll>;using vvvll = vector<vvll>;using vvd = vector<vd>;using vvvd = vector<vvd>;using vc = vector<char>;using vvc = vector<vc>;using vs = vector<string>;using vvs = vector<vs>;using vvvs = vector<vvs>;using pii = pair<int, int>;using pll = pair<ll, ll>;using umpll = unordered_map<ll, ll>;using umpsl = unordered_map<string, ll>;using mpll = map<ll, ll>;using sll = set<ll>;using msll = multiset<ll>;using heapqll = priority_queue<ll, vll, greater<ll>>;using heapqllrev = priority_queue<ll>;using dll = deque<ll>;/* REP macro */#define _overload4(_1,_2,_3,_4,name,...) name#define _rep(i,n) reps(i,0,n)#define reps(i,a,n) for (ll i = (a); i < (ll)(n); ++i)#define repsp(i,a,n,s) for (ll i = (a); i < (ll)(n); i += s)#define rep(...) _overload4(__VA_ARGS__,repsp, reps,_rep,)(__VA_ARGS__)#define rrep(i, n) reps(i, 1, n + 1)#define repd(i,n) for(ll i=n-1;i>=0;i--)#define rrepd(i,n) for(ll i=n;i>=1;i--)#define repdict(key, value, dict) for (const auto& [key, value] : dict)#define repset(x, st) for(auto x : st)/* define short */#define endl "\n"#define pf emplace_front#define pb emplace_back#define popleft pop_front#define popright pop_back#define mp make_pair#define ump unordered_map#define all(obj) (obj).begin(), (obj).end()#define rall(obj) (obj).rbegin(), (obj).rend()#define len(x) (ll)(x.size())#define MAX(x) *max_element(all(x))#define MIN(x) *min_element(all(x))#define ARGMAX(x) distance(x.begin(), max_element(all(x)))#define ARGMIN(x) distance(x.begin(), min_element(all(x)))#define CLAMP(L, X, R) min(max(L, X), R)#define IN(L, X, R) (L <= X && X <= R)#define SET(x) sll(all(x))#define VEC(x) vll(all(x))#define GET(x) ll x = in_ll();#define GET2(x, y) ll x, y; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1];}#define GET3(x, y, z) ll x, y, z; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2];}#define GET4(x, y, z, a) ll x, y, z, a; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3];}#define GET5(x, y, z, a, b) ll x, y, z, a, b; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4];}#define GET6(x, y, z, a, b, c) ll x, y, z, a, b, c; {vll _A_ = in_lls(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4]; c = _A_[5];}#define GETVLL(x) vll x = in_lls();#define GETVVLL(x, N) vvll x; rep(i, N) {GETVLL(ab); x.pb(ab);}#define GETD(x) ld x = in_d();#define GET2D(x, y) ld x, y; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1];}#define GET3D(x, y, z) ld x, y, z; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2];}#define GET4D(x, y, z, a) ld x, y, z, a; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3];}#define GET5D(x, y, z, a, b) ld x, y, z, a, b; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4];}#define GET6D(x, y, z, a, b, c) ld x, y, z, a, b, c; {vd _A_ = in_ds(); x = _A_[0]; y = _A_[1]; z = _A_[2]; a = _A_[3]; b = _A_[4]; c = _A_[5];}#define GETVD(x) vd x = in_ds();#define GETVVD(x, N) vvd x; rep(i, N) {GETVD(ab); x.pb(ab);}#define GETSTR(x) string x = in_str();#define GETSTRS(x) vs x; x = in_strs();#define GETVVS(x, N) vvs x; rep(i, N) x.pb(in_strs());#define GETVSTR(x, N) vs x; rep(i, N) x.pb(in_str());#define INI(x, vec) auto x = vec[0];#define INI2(x, y, vec) auto x = vec[0], y = vec[1];#define INI3(x, y, z, vec) auto x = vec[0], y = vec[1], z = vec[2];#define INI4(x, y, z, a, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3];#define INI5(x, y, z, a, b, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3], b = vec[4];#define INI6(x, y, z, a, b, c, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3], b = vec[4], c = vec[5];#define SETPERM(x, N) vll x(N); iota(all(x), 0);#define SETPERMS(x, s, N) vll x(N); iota(all(x), s);#define UNUSED(x) ((void)x);#define printF(x) print(x); cout << flush;// [INT|LLONG|DBL|LDBL]_[MAX|MIN] 最大最小表現// 型変換#define CHARSTR(x) (""s + x)#define STRBIN2LL(x) std::stoull(x, nullptr, 2)#define STRLL(x) parse(x)#define STRD(x) std::stod(x)#define CHARLL(x) std::stoll(CHARSTR(x))/* sort */#define SORT(x) stable_sort(all(x))#define RSORT(x) stable_sort(rall(x))#define SORT_IDX(x, idx) stable_sort(all(x), [&](const vll &_a_, const vll &_b_){return _a_[idx] < _b_[idx];})#define RSORT_IDX(x, idx) stable_sort(all(x), [&](const vll &_a_, const vll &_b_){return _a_[idx] > _b_[idx];})#define LB_IDX_VEC(c, x) distance((c).begin(), lower_bound(all(c), x)) // O(log N) x未満の最大値についてその右側のidxが求まる#define UB_IDX_VEC(c, x) distance((c).begin(), upper_bound(all(c), x)) // O(log N) x以上の最小値についてその右側のidxが求まる#define LB_ITR_VEC(c, x) lower_bound(all(c), x)#define UB_ITR_VEC(c, x) upper_bound(all(c), x)// #define LB_IDX_SET(c, x) distance((c).begin(), c.lower_bound(x)) // O(N)// #define UB_IDX_SET(c, x) distance((c).begin(), c.upper_bound(x)) // O(N)#define LB_ITR_SET(c, x) c.lower_bound(x)#define UB_ITR_SET(c, x) c.upper_bound(x)#define LB_ITR_MAP(c, x) c.lower_bound(x)#define UB_ITR_MAP(c, x) c.upper_bound(x)#define KEY_CHANGE(c, k1, k2) { auto i_ = c.extract(k1); i_.key() = k2; c.insert(std::move(i_));}#define EXIST(key, dict) (dict.find(key) != dict.end())#define REV(x) reverse(all(x))namespace // 直値のデフォルトの型をllに。{ll _0 = 0;ll _1 = 1;ll _2 = 2;ll _3 = 3;ll _4 = 4;ll _5 = 5;ll _6 = 6;ll _7 = 7;ll _8 = 8;ll _9 = 9;ll _10 = 10;ll _11 = 11;ll _12 = 12;ll _13 = 13;ll _14 = 14;ll _15 = 15;ll _16 = 16;ll _17 = 17;ll _30 = 30;ll _31 = 31;ll _32 = 32;ll _33 = 33;ll _63 = 63;ll _64 = 64;ll _65 = 65;ll _66 = 66;ll _126 = 126;ll _127 = 127;ll _128 = 128;ll _129 = 129;};void ignore_warning() // ワーニング対策{_0 = _0;_1 = _1;_2 = _2;_3 = _3;_4 = _4;_5 = _5;_6 = _6;_7 = _7;_8 = _8;_9 = _9;_10 = _10;_11 = _11;_12 = _12;_13 = _13;_14 = _14;_15 = _15;_16 = _16;_17 = _17;_30 = _30;_31 = _31;_32 = _32;_33 = _33;_63 = _63;_64 = _64;_65 = _65;_66 = _66;_126 = _126;_127 = _127;_128 = _128;_129 = _129;}/* helper func */std::ostream &operator<<(std::ostream &dest, __int128 value) {std::ostream::sentry s(dest);if (s) {__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = std::end(buffer);do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest;}ll parse(string &s) {ll ret = 0;bool isplus = true;for (ll i = 0; i < s.length(); i++)if ('0' <= s[i] && s[i] <= '9')ret = 10 * ret + s[i] - '0';else if (s[i] == '-')isplus ^= isplus;return isplus ? ret : -ret;}string STR(const vector<char> &cs) {return string(cs.begin(), cs.end());}string RSTR(const vector<char> &cs) {return string(cs.rbegin(), cs.rend());}template <typename T>string STR(T v) {ostringstream ss;ss << v;return ss.str();}ll SUM(const vll &v) {ll total = 0;rep(i, len(v)) {total += v[i];}return total;}template<class... T>constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}template<class... T>constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}// search_length: 走査するベクトル長の上限(先頭から何要素目までを検索対象とするか、1始まりで)template <typename T> inline bool vector_finder(std::vector<T> vec, T element, unsigned int search_length) {auto itr = std::find(vec.begin(), vec.end(), element);size_t index = std::distance( vec.begin(), itr );if (index == vec.size() || index >= search_length) {return false;} else {return true;}}inline void print(const sll& v, string s = " "){bool first = true; for(auto &p : v) { if(first) {first = false; cout << p;} else cout << s << p;} cout << endl;}inline void print(const msll& v, string s = " "){bool first = true; for(auto &p : v) { if(first) {first = false; cout << p;} else cout << s << p;} cout << endl;}template <typename T> inline void print(const vector<T>& v, string s = " "){rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}inline void print(const vvll& v, string s = " "){rep(i, len(v)) print(v[i], s);}template <typename T, typename S> inline void print(const pair<T, S>& p){cout << p.first << " " << p.second << endl;}template <typename T> inline void print(const T& x) {cout << x << endl;}template <typename T, typename S> inline void print(const vector<pair<T, S>>& v){for (auto&& p : v) print(p);}template <typename T, typename S> inline void print(const unordered_map<T, S>& d){for (const auto& [key, value] : d) {cout << key << " "; print(value);}}template <typename T, typename S> inline void print(const map<T, S>& d){for (const auto& [key, value] : d) {cout << key << " "; print(value);}}inline void print(const vc &d) {rep(i, len(d)) cout << d[i]; cout << endl;}// 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書きtemplate <typename T> inline bool chmin(T& a, const T& b) {bool compare = a > b; if (a > b) a = b; return compare;}template <typename T> inline bool chmax(T& a, const T& b) {bool compare = a < b; if (a < b) a = b; return compare;}/* func */inline ll in_ll() {string s; getline(cin, s); return STRLL(s);}inline ld in_d() {string s; getline(cin, s); return STRD(s);}inline string in_str() {string s; getline(cin, s); return s;}inline string YESNO(bool cond) {return cond ? "YES" : "NO";}inline string yesno(bool cond) {return cond ? "yes" : "no";}inline string YesNo(bool cond) {return cond ? "Yes" : "No";}/* debug */namespace debug_print_func {std::ostream& os = std::cerr;template <class Tp> auto has_cbegin(int) -> decltype(std::cbegin(std::declval<Tp>()), std::true_type {});template <class Tp> auto has_cbegin(...) -> std::false_type;template <class Tp> auto has_value_type(int) -> decltype(std::declval<typename Tp::value_type>(), std::true_type {});template <class Tp> auto has_value_type(...) -> std::false_type;template <class Tp>[[maybe_unused]] constexpr bool is_iteratable_container_v = decltype(has_cbegin<Tp>(int {}))::value;template <class Tp>[[maybe_unused]] constexpr bool is_container_v = decltype(has_value_type<Tp>(int {}))::value|| is_iteratable_container_v<Tp>;template <> [[maybe_unused]] constexpr bool is_iteratable_container_v<std::string_view> = false;template <> [[maybe_unused]] constexpr bool is_container_v<std::string_view> = false;#if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)template <> [[maybe_unused]] constexpr bool is_iteratable_container_v<std::string> = false;template <> [[maybe_unused]] constexpr bool is_container_v<std::string> = false;#endiftemplate <class Tp, class... Ts> struct first_element { using type = Tp; };template <class... Ts> using first_t = typename first_element<Ts...>::type;template <class Tp, std::enable_if_t<!decltype(has_value_type<Tp>(int {}))::value, std::nullptr_t> = nullptr>auto check_elem(int) -> decltype(*std::cbegin(std::declval<Tp>()));template <class Tp, std::enable_if_t<decltype(has_value_type<Tp>(int {}))::value, std::nullptr_t> = nullptr>auto check_elem(int) -> typename Tp::value_type;template <class Tp>auto check_elem(...) -> void;template <class Tp> using elem_t = decltype(check_elem<Tp>(int {}));template <class Tp> [[maybe_unused]] constexpr bool is_multidim_container_v = is_container_v<Tp>&& is_container_v<elem_t<Tp>>;template <class Tp> std::enable_if_t<!is_container_v<Tp>> out(const Tp&);void out(const char&);void out(const char*);void out(const std::string_view&);#if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)void out(const std::string&);#endif#ifdef __SIZEOF_INT128__void out(const __int128&);void out(const unsigned __int128&);#endiftemplate <class Tp1, class Tp2> void out(const std::pair<Tp1, Tp2>&);#if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE)template <class... Ts> void out(const std::tuple<Ts...>&);#endif#if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK)template <class... Ts> void out(std::stack<Ts...>);#endif#if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE)template <class... Ts> void out(std::queue<Ts...>);template <class... Ts> void out(std::priority_queue<Ts...>);#endiftemplate <class C>std::enable_if_t<is_iteratable_container_v<C>> out(const C&);template <class Tp> std::enable_if_t<!is_container_v<Tp>> out(const Tp& arg) {os << arg;}void out(const char& arg) {os << '\'' << arg << '\'';}void out(const char* arg) {os << '\"' << arg << '\"';}void out(const ld arg) {if (arg == LDBL_MAX) {os << "∞";} else if (arg == -LDBL_MAX) {os << "-∞";} else {os << arg;}}void out(const std::string_view& arg) {os << '\"' << arg << '\"';}#if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)void out(const std::string& arg) {os << '\"' << arg << '\"';}#endif#ifdef __SIZEOF_INT128__void out(const __int128& arg) {if (arg == ULLONG_MAX) {os << "∞";} else {int sign = (arg < 0) ? (-1) : 1;if (sign == -1) os << '-';__int128 base = sign;while (sign * arg >= sign * base * 10) base *= 10;while (base) {os << static_cast<char>('0' + (arg / base % 10));base /= 10;}}}void out(const unsigned __int128& arg) {if (arg == ULLONG_MAX) {os << "∞";} else {unsigned __int128 base = 1;while (arg >= base * 10) base *= 10;while (base) {os << static_cast<char>('0' + (arg / base % 10));base /= 10;}}}#endiftemplate <class Tp1, class Tp2> void out(const std::pair<Tp1, Tp2>& arg) {os << '(';out(arg.first);os << ", ";out(arg.second);os << ')';}#if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE)template <class T, std::size_t... Is> void print_tuple(const T& arg, std::index_sequence<Is...>) {static_cast<void>(((os << (Is == 0 ? "" : ", "), out(std::get<Is>(arg))), ...));}template <class... Ts> void out(const std::tuple<Ts...>& arg) {os << '(';print_tuple(arg, std::make_index_sequence<sizeof...(Ts)>());os << ')';}#endif#if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK)template <class... Ts> void out(std::stack<Ts...> arg) {if (arg.empty()) {os << "<empty stack>";return;}os << "[ ";while (!arg.empty()) {out(arg.top());os << ' ';arg.pop();}os << ']';}#endif#if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE)template <class... Ts> void out(std::queue<Ts...> arg) {if (arg.empty()) {os << "<empty queue>";return;}os << "[ ";while (!arg.empty()) {out(arg.front());os << ' ';arg.pop();}os << ']';}template <class... Ts> void out(std::priority_queue<Ts...> arg) {if (arg.empty()) {os << "<empty priority_queue>";return;}os << "[ ";while (!arg.empty()) {out(arg.top());os << ' ';arg.pop();}os << ']';}#endiftemplate <class Container>std::enable_if_t<is_iteratable_container_v<Container>> out(const Container& arg) {if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) {os << "<empty container>";return;}os << "[ ";std::for_each(std::cbegin(arg), std::cend(arg), [](const elem_t<Container>& elem) {out(elem);os << ' ';});os << ']';}template <class Tp> std::enable_if_t<!is_multidim_container_v<Tp>>print(std::string_view name, const Tp& arg) {os << name << ": ";out(arg);if constexpr (is_container_v<Tp>)os << '\n';}template <class Tp> std::enable_if_t<is_multidim_container_v<Tp>>print(std::string_view name, const Tp& arg) {os << name << ": ";if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) {os << "<empty multidimensional container>\n";return;}std::for_each(std::cbegin(arg), std::cend(arg),[&name, is_first_elem = true](const elem_t<Tp>& elem) mutable {if (is_first_elem)is_first_elem = false;elsefor (std::size_t i = 0; i < name.length() + 2; i++)os << ' ';out(elem);os << '\n';});}template <class Tp, class... Ts> void multi_print(std::string_view names, const Tp& arg, const Ts&... args) {if constexpr (sizeof...(Ts) == 0) {names.remove_suffix(std::distance(names.crbegin(),std::find_if_not(names.crbegin(), names.crend(),[](const char c) { return std::isspace(c); })));print(names, arg);if constexpr (!is_container_v<Tp>)os << '\n';} else {std::size_t comma_pos = 0;for (std::size_t i = 0, paren_depth = 0, inside_quote = false; i < names.length(); i++) {if (!inside_quote && paren_depth == 0 && i > 0 && names[i - 1] != '\'' && names[i] == ',') {comma_pos = i;break;}if (names[i] == '\"') {if (i > 0 && names[i - 1] == '\\') continue;inside_quote ^= true;}if (!inside_quote && names[i] == '(' && (i == 0 || names[i - 1] != '\''))paren_depth++;if (!inside_quote && names[i] == ')' && (i == 0 || names[i - 1] != '\''))paren_depth--;}const std::size_t first_varname_length = comma_pos - std::distance(names.crend() - comma_pos,std::find_if_not(names.crend() - comma_pos, names.crend(),[](const char c) { return std::isspace(c); }));print(names.substr(0, first_varname_length), arg);if constexpr (!is_container_v<Tp>) {if constexpr (is_container_v<first_t<Ts...>>)os << '\n';elseos << " | ";}const std::size_t next_varname_begins_at = std::distance(names.cbegin(),std::find_if_not(names.cbegin() + comma_pos + 1, names.cend(),[](const char c) { return std::isspace(c); }));names.remove_prefix(next_varname_begins_at);multi_print(names, args...);}}} // namespace debug_print#ifdef LOCAL# define debug(...) cerr << "\033[33m(line:" << __LINE__ << ") " << endl; debug_print_func::multi_print(#__VA_ARGS__, __VA_ARGS__); cerr <<"\033[m";#else# define debug(...) ;#endif/* 標準入力 */vs in_strs(const string &delimiter = " "){string s;getline(cin, s);vs output;bitset<255> delims;for (unsigned char c: delimiter){delims[c] = true;}string::const_iterator beg;bool in_token = false;for( string::const_iterator it = s.cbegin(), end = s.cend(); it != end; ++it ){if( delims[*it] ){if( in_token ){output.pb(beg, it);in_token = false;}}else if( !in_token ){beg = it;in_token = true;}}if( in_token )output.pb(beg, s.cend());return output;}inline vll in_lls(){vll vals;vs tokens = in_strs();for (string i: tokens) vals.pb(STRLL(i));return vals;}inline vd in_ds(){vd vals;vs tokens = in_strs();for (string i: tokens) vals.pb(STRD(i));return vals;}inline vvll in_llss(ll line) // 複数行文字列解析{vvll valss;rep(i, line) valss.pb(in_lls());return valss;}inline vs in_vs(ll line) // 複数行文字列解析{vs vecs;rep(i, line) {vecs.pb(in_str());}return vecs;}inline ll popcnt(ll x) { return __builtin_popcountll(x); }template <typename T, typename U>T ceil(T x, U y) {return (x > 0 ? (x + y - 1) / y : x / y);}template <typename T, typename U>T floor(T x, U y) {return (x > 0 ? x / y : (x - y + 1) / y);}template <typename T>class Counter{public:unordered_map<T, ll> tbl_;ll max_cnt_ = 0;T max_key_;ll min_cnt_ = -1;T min_key_;Counter(const vector<T> &vec) {rep(i, len(vec)) {ll v = ++tbl_[vec[i]];if (max_cnt_ < v) {max_cnt_ = v;max_key_ = vec[i];}}}ll count(T key) {return tbl_[key];}T maxkey() {return max_key_;}ll maxcnt() {return max_cnt_;}T minkey() {if (min_cnt_ == -1) {mincnt();}return min_key_;}ll mincnt() {if (min_cnt_ == -1) {min_key_ = tbl_.begin()->first;min_cnt_ = tbl_.begin()->second;for(auto itr = tbl_.begin(); itr != tbl_.end(); itr++){if(min_cnt_ > itr->second) {min_key_ = itr->first;min_cnt_ = itr->second;}}}return min_cnt_;}};template <typename T>vector<T> accsum(const vector<T> &vec, ll ansmod = 0) {if (len(vec) == 0) return vector<T>();vector<T> acc = {0};if (ansmod != 0) {rep (i, len(vec)) acc.pb((acc[i] + vec[i]) % ansmod);} else {rep (i, len(vec)) acc.pb(acc[i] + vec[i]);}return acc;}template <typename T>vector<T> accmax(const vector<T> &vec) {if (len(vec) == 0) return vector<T>();vector<T> acc = {vec[0]};reps (i, 1, len(vec)) acc.pb(max(acc[i - 1], vec[i]));return acc;}template <typename T>vector<T> accmin(const vector<T> &vec) {if (len(vec) == 0) return vector<T>();vector<T> acc = {vec[0]};reps (i, 1, len(vec)) acc.pb(min(acc[i - 1], vec[i]));return acc;}// https://howardhinnant.github.io/combinations.htmlnamespace howardhinnantdetail{// Rotates two discontinuous ranges to put *first2 where *first1 is.// If last1 == first2 this would be equivalent to rotate(first1, first2, last2),// but instead the rotate "jumps" over the discontinuity [last1, first2) -// which need not be a valid range.// In order to make it faster, the length of [first1, last1) is passed in as d1,// and d2 must be the length of [first2, last2).// In a perfect world the d1 > d2 case would have used swap_ranges and// reverse_iterator, but reverse_iterator is too inefficient.template <class BidirIter>voidrotate_discontinuous(BidirIter first1, BidirIter last1,typename std::iterator_traits<BidirIter>::difference_type d1,BidirIter first2, BidirIter last2,typename std::iterator_traits<BidirIter>::difference_type d2){using std::swap;if (d1 <= d2)std::rotate(first2, std::swap_ranges(first1, last1, first2), last2);else{BidirIter i1 = last1;while (first2 != last2)swap(*--i1, *--last2);std::rotate(first1, i1, last1);}}// Rotates the three discontinuous ranges to put *first2 where *first1 is.// Just like rotate_discontinuous, except the second range is now represented by// two discontinuous ranges: [first2, last2) + [first3, last3).template <class BidirIter>voidrotate_discontinuous3(BidirIter first1, BidirIter last1,typename std::iterator_traits<BidirIter>::difference_type d1,BidirIter first2, BidirIter last2,typename std::iterator_traits<BidirIter>::difference_type d2,BidirIter first3, BidirIter last3,typename std::iterator_traits<BidirIter>::difference_type d3){rotate_discontinuous(first1, last1, d1, first2, last2, d2);if (d1 <= d2)rotate_discontinuous(std::next(first2, d2 - d1), last2, d1, first3, last3, d3);else{rotate_discontinuous(std::next(first1, d2), last1, d1 - d2, first3, last3, d3);rotate_discontinuous(first2, last2, d2, first3, last3, d3);}}// Call f() for each combination of the elements [first1, last1) + [first2, last2)// swapped/rotated into the range [first1, last1). As long as f() returns// false, continue for every combination and then return [first1, last1) and// [first2, last2) to their original state. If f() returns true, return// immediately.// Does the absolute mininum amount of swapping to accomplish its task.// If f() always returns false it will be called (d1+d2)!/(d1!*d2!) times.template <class BidirIter, class Function>boolcombine_discontinuous(BidirIter first1, BidirIter last1,typename std::iterator_traits<BidirIter>::difference_type d1,BidirIter first2, BidirIter last2,typename std::iterator_traits<BidirIter>::difference_type d2,Function& f,typename std::iterator_traits<BidirIter>::difference_type d = 0){typedef typename std::iterator_traits<BidirIter>::difference_type D;using std::swap;if (d1 == 0 || d2 == 0)return f();if (d1 == 1){for (BidirIter i2 = first2; i2 != last2; ++i2){if (f())return true;swap(*first1, *i2);}}else{BidirIter f1p = std::next(first1);BidirIter i2 = first2;for (D d22 = d2; i2 != last2; ++i2, --d22){if (combine_discontinuous(f1p, last1, d1-1, i2, last2, d22, f, d+1))return true;swap(*first1, *i2);}}if (f())return true;if (d != 0)rotate_discontinuous(first1, last1, d1, std::next(first2), last2, d2-1);elserotate_discontinuous(first1, last1, d1, first2, last2, d2);return false;}// A binder for binding arguments to call combine_discontinuoustemplate <class Function, class BidirIter>class call_combine_discontinuous{typedef typename std::iterator_traits<BidirIter>::difference_type D;Function f_;BidirIter first1_;BidirIter last1_;D d1_;BidirIter first2_;BidirIter last2_;D d2_;public:call_combine_discontinuous(BidirIter first1, BidirIter last1,D d1,BidirIter first2, BidirIter last2,D d2,Function& f): f_(f), first1_(first1), last1_(last1), d1_(d1),first2_(first2), last2_(last2), d2_(d2) {}bool operator()(){return combine_discontinuous(first1_, last1_, d1_, first2_, last2_, d2_, f_);}};// See combine_discontinuous3template <class BidirIter, class Function>boolcombine_discontinuous3_(BidirIter first1, BidirIter last1,typename std::iterator_traits<BidirIter>::difference_type d1,BidirIter first2, BidirIter last2,typename std::iterator_traits<BidirIter>::difference_type d2,BidirIter first3, BidirIter last3,typename std::iterator_traits<BidirIter>::difference_type d3,Function& f,typename std::iterator_traits<BidirIter>::difference_type d = 0){typedef typename std::iterator_traits<BidirIter>::difference_type D;using std::swap;if (d1 == 1){for (BidirIter i2 = first2; i2 != last2; ++i2){if (f())return true;swap(*first1, *i2);}if (f())return true;swap(*first1, *std::prev(last2));swap(*first1, *first3);for (BidirIter i2 = std::next(first3); i2 != last3; ++i2){if (f())return true;swap(*first1, *i2);}}else{BidirIter f1p = std::next(first1);BidirIter i2 = first2;for (D d22 = d2; i2 != last2; ++i2, --d22){if (combine_discontinuous3_(f1p, last1, d1-1, i2, last2, d22, first3,last3, d3, f, d+1))return true;swap(*first1, *i2);}i2 = first3;for (D d22 = d3; i2 != last3; ++i2, --d22){if (combine_discontinuous(f1p, last1, d1-1, i2, last3, d22, f, d+1))return true;swap(*first1, *i2);}}if (f())return true;if (d1 == 1)swap(*std::prev(last2), *first3);if (d != 0){if (d2 > 1)rotate_discontinuous3(first1, last1, d1, std::next(first2), last2, d2-1, first3, last3, d3);elserotate_discontinuous(first1, last1, d1, first3, last3, d3);}elserotate_discontinuous3(first1, last1, d1, first2, last2, d2, first3, last3, d3);return false;}// Like combine_discontinuous, but swaps/rotates each combination out of// [first1, last1) + [first2, last2) + [first3, last3) into [first1, last1).// If f() always returns false, it is called (d1+d2+d3)!/(d1!*(d2+d3)!) times.template <class BidirIter, class Function>boolcombine_discontinuous3(BidirIter first1, BidirIter last1,typename std::iterator_traits<BidirIter>::difference_type d1,BidirIter first2, BidirIter last2,typename std::iterator_traits<BidirIter>::difference_type d2,BidirIter first3, BidirIter last3,typename std::iterator_traits<BidirIter>::difference_type d3,Function& f){typedef call_combine_discontinuous<Function&, BidirIter> F;F fbc(first2, last2, d2, first3, last3, d3, f); // BCreturn combine_discontinuous3_(first1, last1, d1, first2, last2, d2, first3, last3, d3, fbc);}// See permutetemplate <class BidirIter, class Function>boolpermute_(BidirIter first1, BidirIter last1,typename std::iterator_traits<BidirIter>::difference_type d1,Function& f){using std::swap;switch (d1){case 0:case 1:return f();case 2:if (f())return true;swap(*first1, *std::next(first1));return f();case 3:{if (f())return true;BidirIter f2 = std::next(first1);BidirIter f3 = std::next(f2);swap(*f2, *f3);if (f())return true;swap(*first1, *f3);swap(*f2, *f3);if (f())return true;swap(*f2, *f3);if (f())return true;swap(*first1, *f2);swap(*f2, *f3);if (f())return true;swap(*f2, *f3);return f();}}BidirIter fp1 = std::next(first1);for (BidirIter p = fp1; p != last1; ++p){if (permute_(fp1, last1, d1-1, f))return true;std::reverse(fp1, last1);swap(*first1, *p);}return permute_(fp1, last1, d1-1, f);}// Calls f() for each permutation of [first1, last1)// Divided into permute and permute_ in a (perhaps futile) attempt to// squeeze a little more performance out of it.template <class BidirIter, class Function>boolpermute(BidirIter first1, BidirIter last1,typename std::iterator_traits<BidirIter>::difference_type d1,Function& f){using std::swap;switch (d1){case 0:case 1:return f();case 2:{if (f())return true;BidirIter i = std::next(first1);swap(*first1, *i);if (f())return true;swap(*first1, *i);}break;case 3:{if (f())return true;BidirIter f2 = std::next(first1);BidirIter f3 = std::next(f2);swap(*f2, *f3);if (f())return true;swap(*first1, *f3);swap(*f2, *f3);if (f())return true;swap(*f2, *f3);if (f())return true;swap(*first1, *f2);swap(*f2, *f3);if (f())return true;swap(*f2, *f3);if (f())return true;swap(*first1, *f3);}break;default:BidirIter fp1 = std::next(first1);for (BidirIter p = fp1; p != last1; ++p){if (permute_(fp1, last1, d1-1, f))return true;std::reverse(fp1, last1);swap(*first1, *p);}if (permute_(fp1, last1, d1-1, f))return true;std::reverse(first1, last1);break;}return false;}// Creates a functor with no arguments which calls f_(first_, last_).// Also has a variant that takes two It and ignores them.template <class Function, class It>class bound_range{Function f_;It first_;It last_;public:bound_range(Function f, It first, It last): f_(f), first_(first), last_(last) {}booloperator()(){return f_(first_, last_);}booloperator()(It, It){return f_(first_, last_);}};// A binder for binding arguments to call permutetemplate <class Function, class It>class call_permute{typedef typename std::iterator_traits<It>::difference_type D;Function f_;It first_;It last_;D d_;public:call_permute(Function f, It first, It last, D d): f_(f), first_(first), last_(last), d_(d) {}booloperator()(){return permute(first_, last_, d_, f_);}};} // detailtemplate <class BidirIter, class Function>Functionfor_each_combination(BidirIter first, BidirIter last,BidirIter mid, Function f){howardhinnantdetail::bound_range<Function&, BidirIter> wfunc(f, first, mid);howardhinnantdetail::combine_discontinuous(first, mid, std::distance(first, mid),mid, last, std::distance(mid, last),wfunc);return f;}class BitwiseFullSearch{public:ll count_;std::function<void(const vll &ptn, ll &count)> checkcount_; // カウントするロジックのラムダ式を突っ込む。BitwiseFullSearch(std::function<void(const vll &ptn, ll &count)> f) : count_(0), checkcount_(f) {}// ここは触らなくてよい(パターンを列挙しているだけ)bool operator()(vll::iterator it1, vll::iterator it2){vll ptn;while (it1 != it2){ptn.pb(*it1);++it1;}checkcount_(ptn, count_);return false;}};ll _comb_ptn_count(ll R, const std::function<void(const vll &ptn, ll &count)> &f, vll &_A_) {auto B = BitwiseFullSearch(f);vll::iterator _R_ = _A_.begin() + R;B = for_each_combination(all(_A_), _R_, B);return B.count_;}ll comb_ptn_count(ll N, ll R, const std::function<void(const vll &ptn, ll &count)> &f) {SETPERM(_A_, N);return _comb_ptn_count(R, f, _A_);}vvll get_comb_ptn(ll N, ll R) {vvll cb;auto f = [&](const vll &ptn, ll &count){UNUSED(count);cb.pb(ptn);};comb_ptn_count(N, R, f);return cb;}ll comb_allptn_count(ll N, const std::function<void(const vll &ptn, ll &count)> &f) {ll cnt = 0;SETPERM(_A_, N);rep(r, N + 1) {cnt += _comb_ptn_count(r, f, _A_);}return cnt;}// N が 20とかだとSegmentation faultが発生する。スタック領域が足りなくなるか。vvll get_comb_allptn(ll N) {vvll cb;auto f = [&](const vll &ptn, ll &count){UNUSED(count);cb.pb(ptn);};comb_allptn_count(N, f);return cb;}vvll get_perm_ptn(ll N) {vvll ptn;SETPERM(_A_, N);do {ptn.pb(_A_);} while(next_permutation(all(_A_)));return ptn;}// n個からr個有効にしたbitパターンの数値を列挙// 下1桁目から0, 1, 2番目が有効無効を表す。(Nは60くらいまで)vll get_bitptn(ll N, ll R) {vll bitptns;auto ptns = get_comb_ptn(N, R);rep (i, len(ptns)) {ll bitptn = 0;rep (j, R) {bitptn += _1 << ptns[i][j];}bitptns.pb(bitptn);}return bitptns;}inline ll sumk(ll n){return n * (n + 1) / 2;}inline ll sumk2(ll n){return n * (n + 1) * (2 * n + 1) / 6;}ll POW(ll n, ll r){if (r == 0) return 1;else if (r % 2 == 0) return POW(n * n, (ll)(r / 2));else return n * POW(n, r - 1);}inline string alpha(){return "abcdefghijklmnopqrstuvwxyz";}inline ll alpha_num(char c){return ll(c) - ll('a');}inline string alpha_big(){return "ABCDEFGHIJKLMNOPQRSTUVWXYZ";}inline ll alpha_big_num(char c){return ll(c) - ll('A');}inline char alpha_big2small(char C) {static string s = alpha();ll idx = alpha_big_num(C);return IN(0, idx, 25) ? s[idx] : C;}inline char alpha_small2big(char c) {static string s = alpha_big();ll idx = alpha_num(c);return IN(0, idx, 25) ? s[idx] : c;}string zerofill(ll v, ll outputlen){string s = STR(v);string zerostr(outputlen - len(s), '0');return zerostr + s;}// ランレングス圧縮// auto rle = RunLengthEncoding(S);// rep(i, len(rle)) {// auto &[c, cnt] = rle[i];// }vector<pair<char, ll>> RunLengthEncoding(const string &s) {vector<pair<char, ll>> tbl;char c = s[0];ll cnt = 1;ll N = len(s);reps (i, 1, N) {if (c == s[i]) {cnt++;}else {tbl.pb(mp(c, cnt));c = s[i];cnt = 1;}}tbl.pb(mp(c, cnt));return tbl;}// 約数個数列挙(MAXNまで)vll divisors_count(ll MAXN = 1000000){vll div = vll(MAXN + 1, 0);rrep(n, MAXN) repsp(m, n, MAXN + 1, n) {div[m] += 1;}return div;}// Nの階乗がkで何回割れるかを返す。(ルジャンドルの公式)ll LegendresFormula(ll N, ll k) {ll v = k;ll cnt = 0;while(v <= N) {cnt += floor(N, v);v *= k;}return cnt;}// 約数列挙// 約数の個数は大体n^(1/3)個vll make_divisors(ll n) {vll divisors;for(ll i = 1; i * i <= n; ++i) {if(n % i == 0) {divisors.pb(i);if(i != n / i) {divisors.pb(n / i);}}}return divisors;}// N以下の素数列挙(Nはせいぜい10^7くらいまで)inline vll eratosthenes(ll N) {vll ps;vector<bool> primes(N + 1);rep(i, len(primes)) primes[i] = true;primes[0] = primes[1] = false;rep(i, len(primes)) {if (primes[i]) {ps.pb(i);for (ull j = i + i; j < len(primes); j += i) {primes[j] = false;}}}return ps;}// 高速素因数分解(MAXNの範囲まで)class Prime{public:static vll sieve; // 何回もPrimeのインスタンスを生成するときはstaticをはずして、下の実体もコメントアウトする。Prime(ll MAXN = 10000000) {rep(i, MAXN + 1) sieve.pb(i);ll p = 2;while (p * p <= MAXN) {if (sieve[p] == p) {repsp(q, 2 * p, MAXN + 1, p) {if (sieve[q] == q) sieve[q] = p;}}p += 1;}}Counter<ll> prime(ll n) {if (n == 1) return Counter<ll>(vll());vll tmp;while (n > 1) {tmp.pb(sieve[n]);n = (ll)(n / sieve[n]);}return Counter<ll>(tmp);}};vll Prime::sieve = vll();#define mod_m2p(a, m) (((m) + (a)) % (m))#define mod_add(a, b, m) (((a) + (b)) % (m))#define mod_sub(a, b, m) (((m) + (a) - (b)) % (m))#define mod_mul(a, b, m) (mod_m2p(((a) % (m)) * ((b) % (m)), (m)))ll mod_bipow_(ll x, ll y, ll m) { // x^y by bisection methodif (y == 0) return 1 % m;else if (y == 1) return x % m;else if (y % 2 == 0) {ll val = mod_bipow_(x, (ll)(y / 2), m);return mod_mul(val, val, m);} else {ll val = mod_bipow_(x, (ll)(y / 2), m);return mod_mul(mod_mul(val, val, m), x, m);}}ll mod_inv(ll x, ll pm) { return mod_bipow_(mod_m2p(x, pm), pm - 2, pm); } // x^{-1} = x^{MOD-2} (MOD: prime number)ll mod_div(ll a, ll b, ll m) { return mod_mul(mod_m2p(a, m), mod_inv(mod_m2p(b, m), m), m); } // a/b = a*b^{-1}ll mod_bipow(ll x, ll y, ll m) {if (y < 0) {ll xx = mod_div((ll)1, x, m);return mod_bipow_(xx, -y, m);}return mod_bipow_(x, y, m);}ll mysqrt(ll n) {ll ok = 0, ng = n + 1;while (ng - ok > 1) {ll mid = (ng + ok) >> 1;if (mid * mid <= n) {ok = mid;} else {ng = mid;}}return ok;}// nCkをmで割った余りを求めるclass Combination {const ll n_;const ll m_;vll facts_;vll inv_facts_;public:Combination(ll N, ll mod) : n_(2 * N), m_(mod), facts_(n_ + 1), inv_facts_(n_ + 1) {rep(i, n_ + 1) facts_[i] = i == 0 ? 1 : mod_mul(facts_[i - 1], i, m_);for (ll i = n_; i >= 0; i--) inv_facts_[i] = i == n_ ? mod_inv(facts_[n_], m_) : mod_mul(inv_facts_[i + 1], i + 1, m_); // (i!)^{-1}=((i+1)!)^{-1}*(i+1)}ll nPr(ll n, ll r) {if (n < r) return _0;return mod_mul(facts_[n], inv_facts_[n - r], m_);}ll nCr(ll n, ll r) {if (n < r) return _0;return mod_mul(facts_[n], mod_mul(inv_facts_[r], inv_facts_[n - r], m_), m_);}ll nHr(ll n, ll r) {return nCr(n + r - 1, r);}ll catalan(ll n) { // https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0return mod_mul(nCr(2 * n, n), mod_inv(n + 1, m_), m_);}// カタラン数・・・(2n C n)/(n + 1) = (2n C n) - (2n C n-1)// c0 = 1, c_n = rep(i, n) c[i] * c[n - i - 1]// c0から順に1,1,2,5,14,42,132,429,1430,...// 1 <= a1 <= a2 <= a3 <= a4 <= ... <= ak <= Nの組み合わせの数。// CombinationのコンストラクタにN + Kを入れておくこと。ll loopcnt(ll n, ll k) {assert(n + k <= n_);return nCr(n - 1 + k, n - 1);}};// 1-originで扱う。class UnionFind {ll n_;vll size_;vll par_;vll link_;vll rank_;vll par_diff_;public:UnionFind(ll n) : n_(n + 1), size_(n_, 1), par_(n_), link_(n_), rank_(n_), par_diff_(n_){iota(all(par_), 0);iota(all(link_), 0);}ll find(ll x) {if (par_[x] == x) return x;else {ll ret = find(par_[x]);if (par_diff_[par_[x]] == LLONG_MAX) par_diff_[x] = LLONG_MAX;else par_diff_[x] += par_diff_[par_[x]];return par_[x] = ret;}}ll operator[](ll x) { return find(x); }bool unite(ll x, ll y, ll w = 0) {if (x != 0 && same(x, y) && diff(x, y) != w) unite(0, y);ll rx = find(x);ll ry = find(y);ll wt = w;wt += weight(x);wt -= weight(y);if (rx == ry) {return false;}if (ry < rx) {swap(rx, ry);wt = -wt;}size_[rx] += size_[ry];if (rank_[rx] == rank_[ry]) rank_[rx]++;size_[ry] = 0;par_[ry] = rx;par_diff_[ry] = wt;swap(link_[rx], link_[ry]);return true;}vll find_all() {vll A(n_);rep(i, n_) A[i] = find(i);return A;}vll members(ll x) {vll mems = vll{x};for (ll y = link_[x]; y != x; y = link_[y]) mems.pb(y);return mems;}ll size(ll x) {return size_[find(x)];}bool same(ll x, ll y) {return find(x) == find(y);}vll roots() {vll rs;reps(i, 1, n_) if (size_[i] > 0) rs.pb(i);return rs;}ll group_count() {return len(roots());}unordered_map<ll, vll> all_group_members() {unordered_map<ll, vll> group_members;reps(member, 1, n_) group_members[find(member)].pb(member);return group_members;}ll weight(ll x) {find(x);return par_diff_[x];}ll diff(ll x, ll y) {if (same(0, x) || same(0, y)) return LLONG_MAX;return weight(y) - weight(x);}};class Graph{private:unordered_map<ll, vector<pll>> edges_;unordered_map<ll, vector<pll>> ignore_edges_; // 多重辺で同じ重みの辺があるとダメvll outdeg_;vll indeg_;const ll V_;const bool dir_;const ll ansmod_;// dist(-1で初期化), cntは呼び出し元でN個分の配列を与えること。connect_vtxsは空のvectorでよい。void bfs_(ll sv, vll &dist, vll &connect_vtxs, vll &cnt, vll &root, ll search_depth = 1000000000){if (dist[sv] != -1) return;dll q = dll();q.pb(sv);dist[sv] = 0;connect_vtxs.pb(sv);cnt[sv] = 1;if (search_depth == 0) return;while (len(q) > 0) {ll p = q[0];q.popleft();if (!EXIST(p, edges_)) continue;vector<pll> &evw = edges_[p];for (const auto& [ev, w] : evw) {bool isignore = false;rep(i, len(ignore_edges_[p])) {const auto& [igev, igw] = ignore_edges_[p][i];if (ev == igev && w == igw) {isignore = true;}}if (isignore) continue;if (dist[ev] != -1) {if (dist[ev] == dist[p] + 1) {cnt[ev] += cnt[p];cnt[ev] %= ansmod_;}continue;}dist[ev] = dist[p] + 1;root[ev] = p;cnt[ev] = cnt[p];connect_vtxs.pb(ev);if (dist[ev] < search_depth){if (w == 0) q.pf(ev);else q.pb(ev);}}}}// 木で無向辺のみ対応void dfs_(ll sv, ll pre = -1) {connect_vtxs_.pb(sv);root_[sv] = pre;traverse_preorder_path_.pb(sv);vector<pll> &evw = edges_[sv];ll child_cnt = 0;for (const auto& [ev, w] : evw) {if (ev == pre) continue;bool isignore = false; // 無効化されている辺は無視する。rep(i, len(ignore_edges_[sv])) {const auto& [igev, igw] = ignore_edges_[sv][i];if (ev == igev && w == igw) {isignore = true;}}if (isignore) continue;dfs_(ev, sv);child_cnt++;}if (child_cnt == 0) { // 辺が1つのときで根でないときtraverse_reached_[sv] = true;traverse_inorder_path_.pb(sv);}if (pre != -1 && !traverse_reached_[pre]) {traverse_reached_[pre] = true;traverse_inorder_path_.pb(pre);}traverse_postorder_path_.pb(sv);}public:vll path_; // dfsでたどった経路vll traverse_preorder_path_; // dfsでたどり着けるノード順 (行きがけ順)vll traverse_inorder_path_; // dfsでたどり着けるノード順 (通りがけ順)vll traverse_postorder_path_; // dfsでたどり着けるノード順 (帰りがけ順) (木DPで使えそう)vector<bool> traverse_reached_; // dfsでたどり着いたチェックvll dist_;vll connect_vtxs_;vll cnt_;vll root_;Graph(ll V, bool dir, ll ansmod = 1000000007) : V_(V), dir_(dir), ansmod_(ansmod), traverse_reached_(V_, false), dist_(V_, -1), cnt_(V_), root_(V_, -1){outdeg_ = vll(V);indeg_ = vll(V);}void append_edge(ll sv, ll ev, ll weight = 1){vector<pll> &u = edges_[sv];pll v = make_pair(ev, weight);u.pb(v);outdeg_[sv]++;indeg_[ev]++;if (!dir_) {swap(sv, ev);outdeg_[sv]++;indeg_[ev]++;vector<pll> &ru = edges_[sv];pll rv = make_pair(ev, weight);ru.pb(rv);}}void ignore_edge(ll sv, ll ev, ll weight = 1) {vector<pll> &u = ignore_edges_[sv];pll v = make_pair(ev, weight);u.pb(v);if (!dir_) {swap(sv, ev);vector<pll> &ru = ignore_edges_[sv];pll rv = make_pair(ev, weight);ru.pb(rv);}}void ignore_edge_clear() {ignore_edges_.clear();}void bfs(ll sv, bool reset = true, ll search_depth = 1000000000) {if (reset) {rep(i, len(connect_vtxs_)) {dist_[connect_vtxs_[i]] = -1;cnt_[connect_vtxs_[i]] = 0;root_[connect_vtxs_[i]] = -1;}connect_vtxs_.clear();}bfs_(sv, dist_, connect_vtxs_, cnt_, root_, search_depth);}void dfs(ll sv, bool reset = false) {if (traverse_reached_[sv]) return; // すでに到達済みの点はdfsしないif (reset) {traverse_preorder_path_.clear();traverse_inorder_path_.clear();traverse_postorder_path_.clear();rep(i, len(connect_vtxs_)) {traverse_reached_[connect_vtxs_[i]] = false; // 「他の始点から到達してたときは無視したい」場合はこれをコメントアウトroot_[connect_vtxs_[i]] = -1;}connect_vtxs_.clear();}dfs_(sv);}vll topo_sort(){heapqll q;vll to = vll(V_);vll topo_vertex_list;repdict(u, vtxs, edges_) {for (const auto& [ev, w] : vtxs) {++to[ev];}}rep(i, V_) {if (to[i] != 0) continue;q.push(i);}while (len(q) != 0) {const ll v = q.top();q.pop();topo_vertex_list.pb(v);for (const auto [ev, w] : edges_[v]) {--to[ev];if (to[ev]) continue;q.push(ev);}}return topo_vertex_list;}ll longest_path() { // 有向グラフで非連結グラフの最大パスの長さを求める。dll q;vll dist(V_);rep (i, V_) {if (indeg_[i] == 0) q.pb(i);}while (len(q) != 0) {const ll u = q.front();q.pop_front();vector<pll> &v = edges_[u];rep (i, len(v)) {chmax(dist[v[i].first], dist[u] + 1);indeg_[v[i].first]--;if (indeg_[v[i].first] == 0) q.pb(v[i].first);}}return MAX(dist);}// 無向グラフのみ対応。// start->endのパスが無ければ空を返すvll get_path(ll start, ll end, ll vertexidx_offset = 0) {bfs(start);if (dist_[end] == -1) return vll{};ll pos = end;vll path = {end + vertexidx_offset};while(pos != start) {pos = root_[pos];path.pb(pos + vertexidx_offset);}REV(path);return path;}// 先にbfsを実行しておく。vll parts_tree_size() {vvll tmp;rep (i, V_) {tmp.pb(vll{dist_[i], i});}SORT(tmp);REV(tmp);vll ans(V_);rep (i, V_) {INI2(d, idx, tmp[i]);UNUSED(d);if (root_[idx] != -1) ans[root_[idx]] += ans[idx] + 1;}return ans;}};#include __FILE__#endif