#ifdef INCLUDED_MAIN // const ll ansmod = 998244353; // const ll ansmod = 1000000007; // [lidx, ridx)の区間の文字列を取得 substr("0123456789", 2, 6) -> "2345" // 第3引数は文字数ではない string substr(const string &s, ll lidx, ll ridx) { if (ridx <= lidx) return ""; return s.substr(lidx, ridx - lidx); } auto solve() { GETSTR(S); string T = S; REV(T); if (S == T) return len(S); ll N = len(S); vector> memo(N + 10, vector(N + 10, -1)); vector> memo2(N + 10, vector(N + 10, -1)); auto ff = [&](auto &&f, ll n, ll idx) { if (len(S) < n + idx) return false; if (memo2[n][idx] != -1) return memo2[n][idx] == 1; rep(i, n, len(S)) { if (memo[idx][i] == 0) continue; if (len(S) < idx + i) break; if (memo[idx][i] == 1 && memo2[n][idx + i] != -1) return memo2[n][idx + i] == 1; bool isPalindrome = true; if (memo[idx][i] == -1) { rep(j, i / 2) { if (S[idx + j] != S[idx + i - j - 1]) { isPalindrome = false; break; } } memo[idx][i] = isPalindrome; } if (!isPalindrome) continue; if (memo2[n][idx + i] == -1) { if (len(S) != idx + i) isPalindrome = f(f, n, idx + i); memo2[n][idx + i] = isPalindrome; } else { isPalindrome = memo2[n][idx + i]; } if (isPalindrome) return true; } memo2[n][idx] = false; return false; }; rrepd(n, len(S)) { if (n == 1) break; if (ff(ff, n, 0)) return n; } return _1; } 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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #endif using namespace std; // clang-format off /* accelration */ // 高速バイナリ生成 #ifndef LOCAL #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif // unordered_mapでpair, vector, tupleをkeyにするためのコード // (参考文献) https://qiita.com/hamamu/items/4d081751b69aa3bb3557 template size_t HashCombine(const size_t seed,const T &v){ return seed^(std::hash()(v)+0x9e3779b9+(seed<<6)+(seed>>2)); } /* pair用 */ template struct std::hash>{ size_t operator()(const std::pair &keyval) const noexcept { return HashCombine(std::hash()(keyval.first), keyval.second); } }; /* vector用 */ template struct std::hash>{ size_t operator()(const std::vector &keyval) const noexcept { size_t s=0; for (auto&& v: keyval) s=HashCombine(s,v); return s; } }; /* deque用 */ template struct std::hash>{ size_t operator()(const std::deque &keyval) const noexcept { size_t s=0; for (auto&& v: keyval) s=HashCombine(s,v); return s; } }; /* tuple用 */ template struct HashTupleCore{ template size_t operator()(const Tuple &keyval) const noexcept{ size_t s=HashTupleCore()(keyval); return HashCombine(s,std::get(keyval)); } }; template <> struct HashTupleCore<0>{ template size_t operator()(const Tuple &keyval) const noexcept{ return 0; } }; template struct std::hash>{ size_t operator()(const tuple &keyval) const noexcept { return HashTupleCore>::value>()(keyval); } }; /* alias */ using ull = __uint128_t; // using ll = long long; // __int128でTLEするときに切り替える。 using ll = __int128; using ld = long double; using vi = vector; using vl = vector; using vll = vector; using vd = vector; using vvi = vector; using vvl = vector; using vvll = vector; using vvvll = vector; using vvd = vector; using vvvd = vector; using vc = vector; using vvc = vector; using vs = vector; using vvs = vector; using vvvs = vector; using pii = pair; using pll = pair; using umpll = unordered_map; using umpsl = unordered_map; using mpll = map; using sll = set; using msll = multiset; using heapqll = priority_queue>; using heapqllrev = priority_queue; using dll = deque; /* 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 &cs) { return string(cs.begin(), cs.end()); } string RSTR(const vector &cs) { return string(cs.rbegin(), cs.rend()); } template 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 constexpr auto min(T... a){ return min(initializer_list>{a...}); } template constexpr auto max(T... a){ return max(initializer_list>{a...}); } // search_length: 走査するベクトル長の上限(先頭から何要素目までを検索対象とするか、1始まりで) template inline bool vector_finder(std::vector 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 inline void print(const vector& 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 inline void print(const pair& p) {cout << p.first << " " << p.second << endl;} template inline void print(const T& x) {cout << x << endl;} template inline void print(const vector>& v) {for (auto&& p : v) print(p);} template inline void print(const unordered_map& d) {for (const auto& [key, value] : d) {cout << key << " "; print(value);}} template inline void print(const map& 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 inline bool chmin(T& a, const T& b) {bool compare = a > b; if (a > b) a = b; return compare;} template 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 auto has_cbegin(int) -> decltype(std::cbegin(std::declval()), std::true_type {}); template auto has_cbegin(...) -> std::false_type; template auto has_value_type(int) -> decltype(std::declval(), std::true_type {}); template auto has_value_type(...) -> std::false_type; template [[maybe_unused]] constexpr bool is_iteratable_container_v = decltype(has_cbegin(int {}))::value; template [[maybe_unused]] constexpr bool is_container_v = decltype(has_value_type(int {}))::value || is_iteratable_container_v; template <> [[maybe_unused]] constexpr bool is_iteratable_container_v = false; template <> [[maybe_unused]] constexpr bool is_container_v = false; #if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING) template <> [[maybe_unused]] constexpr bool is_iteratable_container_v = false; template <> [[maybe_unused]] constexpr bool is_container_v = false; #endif template struct first_element { using type = Tp; }; template using first_t = typename first_element::type; template (int {}))::value, std::nullptr_t> = nullptr> auto check_elem(int) -> decltype(*std::cbegin(std::declval())); template (int {}))::value, std::nullptr_t> = nullptr> auto check_elem(int) -> typename Tp::value_type; template auto check_elem(...) -> void; template using elem_t = decltype(check_elem(int {})); template [[maybe_unused]] constexpr bool is_multidim_container_v = is_container_v && is_container_v>; template std::enable_if_t> 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&); #endif template void out(const std::pair&); #if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE) template void out(const std::tuple&); #endif #if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK) template void out(std::stack); #endif #if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE) template void out(std::queue); template void out(std::priority_queue); #endif template std::enable_if_t> out(const C&); template std::enable_if_t> 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('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('0' + (arg / base % 10)); base /= 10; } } } #endif template void out(const std::pair& arg) { os << '('; out(arg.first); os << ", "; out(arg.second); os << ')'; } #if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE) template void print_tuple(const T& arg, std::index_sequence) { static_cast(((os << (Is == 0 ? "" : ", "), out(std::get(arg))), ...)); } template void out(const std::tuple& arg) { os << '('; print_tuple(arg, std::make_index_sequence()); os << ')'; } #endif #if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK) template void out(std::stack arg) { if (arg.empty()) { os << ""; return; } os << "[ "; while (!arg.empty()) { out(arg.top()); os << ' '; arg.pop(); } os << ']'; } #endif #if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE) template void out(std::queue arg) { if (arg.empty()) { os << ""; return; } os << "[ "; while (!arg.empty()) { out(arg.front()); os << ' '; arg.pop(); } os << ']'; } template void out(std::priority_queue arg) { if (arg.empty()) { os << ""; return; } os << "[ "; while (!arg.empty()) { out(arg.top()); os << ' '; arg.pop(); } os << ']'; } #endif template std::enable_if_t> out(const Container& arg) { if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) { os << ""; return; } os << "[ "; std::for_each(std::cbegin(arg), std::cend(arg), [](const elem_t& elem) { out(elem); os << ' '; }); os << ']'; } template std::enable_if_t> print(std::string_view name, const Tp& arg) { os << name << ": "; out(arg); if constexpr (is_container_v) os << '\n'; } template std::enable_if_t> print(std::string_view name, const Tp& arg) { os << name << ": "; if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) { os << "\n"; return; } std::for_each(std::cbegin(arg), std::cend(arg), [&name, is_first_elem = true](const elem_t& elem) mutable { if (is_first_elem) is_first_elem = false; else for (std::size_t i = 0; i < name.length() + 2; i++) os << ' '; out(elem); os << '\n'; }); } template 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) 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) { if constexpr (is_container_v>) os << '\n'; else os << " | "; } 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 T ceil(T x, U y) { return (x > 0 ? (x + y - 1) / y : x / y); } template T floor(T x, U y) { return (x > 0 ? x / y : (x - y + 1) / y); } template class Counter { public: unordered_map tbl_; ll max_cnt_ = 0; T max_key_; ll min_cnt_ = -1; T min_key_; Counter(const vector &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 vector accsum(const vector &vec, ll ansmod = 0) { if (len(vec) == 0) return vector(); vector 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 vector accmax(const vector &vec) { if (len(vec) == 0) return vector(); vector acc = {vec[0]}; reps (i, 1, len(vec)) acc.pb(max(acc[i - 1], vec[i])); return acc; } template vector accmin(const vector &vec) { if (len(vec) == 0) return vector(); vector acc = {vec[0]}; reps (i, 1, len(vec)) acc.pb(min(acc[i - 1], vec[i])); return acc; } // https://howardhinnant.github.io/combinations.html namespace 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 void rotate_discontinuous(BidirIter first1, BidirIter last1, typename std::iterator_traits::difference_type d1, BidirIter first2, BidirIter last2, typename std::iterator_traits::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 void rotate_discontinuous3(BidirIter first1, BidirIter last1, typename std::iterator_traits::difference_type d1, BidirIter first2, BidirIter last2, typename std::iterator_traits::difference_type d2, BidirIter first3, BidirIter last3, typename std::iterator_traits::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 bool combine_discontinuous(BidirIter first1, BidirIter last1, typename std::iterator_traits::difference_type d1, BidirIter first2, BidirIter last2, typename std::iterator_traits::difference_type d2, Function& f, typename std::iterator_traits::difference_type d = 0) { typedef typename std::iterator_traits::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); else rotate_discontinuous(first1, last1, d1, first2, last2, d2); return false; } // A binder for binding arguments to call combine_discontinuous template class call_combine_discontinuous { typedef typename std::iterator_traits::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_discontinuous3 template bool combine_discontinuous3_(BidirIter first1, BidirIter last1, typename std::iterator_traits::difference_type d1, BidirIter first2, BidirIter last2, typename std::iterator_traits::difference_type d2, BidirIter first3, BidirIter last3, typename std::iterator_traits::difference_type d3, Function& f, typename std::iterator_traits::difference_type d = 0) { typedef typename std::iterator_traits::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); else rotate_discontinuous(first1, last1, d1, first3, last3, d3); } else rotate_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 bool combine_discontinuous3(BidirIter first1, BidirIter last1, typename std::iterator_traits::difference_type d1, BidirIter first2, BidirIter last2, typename std::iterator_traits::difference_type d2, BidirIter first3, BidirIter last3, typename std::iterator_traits::difference_type d3, Function& f) { typedef call_combine_discontinuous F; F fbc(first2, last2, d2, first3, last3, d3, f); // BC return combine_discontinuous3_(first1, last1, d1, first2, last2, d2, first3, last3, d3, fbc); } // See permute template bool permute_(BidirIter first1, BidirIter last1, typename std::iterator_traits::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 bool permute(BidirIter first1, BidirIter last1, typename std::iterator_traits::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 bound_range { Function f_; It first_; It last_; public: bound_range(Function f, It first, It last) : f_(f), first_(first), last_(last) {} bool operator()() { return f_(first_, last_); } bool operator()(It, It) { return f_(first_, last_); } }; // A binder for binding arguments to call permute template class call_permute { typedef typename std::iterator_traits::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) {} bool operator()() { return permute(first_, last_, d_, f_); } }; } // detail template Function for_each_combination(BidirIter first, BidirIter last, BidirIter mid, Function f) { howardhinnantdetail::bound_range 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 checkcount_; // カウントするロジックのラムダ式を突っ込む。 BitwiseFullSearch(std::function 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 &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 &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 &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> RunLengthEncoding(const string &s) { vector> 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 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 prime(ll n) { if (n == 1) return Counter(vll()); vll tmp; while (n > 1) { tmp.pb(sieve[n]); n = (ll)(n / sieve[n]); } return Counter(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 method if (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%B0 return 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 all_group_members() { unordered_map 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> edges_; unordered_map> 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 &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 &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 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 &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 &ru = edges_[sv]; pll rv = make_pair(ev, weight); ru.pb(rv); } } void ignore_edge(ll sv, ll ev, ll weight = 1) { vector &u = ignore_edges_[sv]; pll v = make_pair(ev, weight); u.pb(v); if (!dir_) { swap(sv, ev); vector &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 &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