#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include "bits/stdc++.h" #ifdef _MSC_VER #include //gcc上ではこれがあると動かない。__popcnt, umul128 等用のincludeファイル。 #define __builtin_popcount __popcnt #define __builtin_popcountll __popcnt64 // 1 の位から何個 0 が連なっているか。(0 入れると 0 を返す。) inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; } inline unsigned int __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; } // 2進での leading 0 の個数。(0 入れると 32, 64 を返す。) inline unsigned int __builtin_clz(unsigned x) { return (unsigned int)__lzcnt(x); } inline unsigned int __builtin_clzll(unsigned long long x) { return (unsigned int)__lzcnt64(x); } #pragma warning(disable : 4996) #pragma intrinsic(_umul128) #endif //#include //using namespace atcoder; using namespace std; //---------- 多倍長関連 ---------- //#include //#include //using namespace boost::multiprecision; typedef long long ll; typedef long double ld; #define int long long #define LL128 boost::multiprecision::int128_t #define LL boost::multiprecision::cpp_int #define LD100 boost::multiprecision::cpp_dec_float_100 #define LD50 boost::multiprecision::cpp_dec_float_50 #define rep(i, n) for(long long i = 0; i < (n); ++i) #define REP(i, s, n) for(long long i = (s); i < (n); ++i) #define rrep(i, n) for(long long i = (n) - 1; i >= 0; --i) #define sqrt(d) pow((ld) (d), 0.50) #define PII pair #define MP make_pair #define PB push_back #define ALL(v) v.begin(), v.end() constexpr int INF2 = std::numeric_limits::max() / 2 - 10000000; constexpr long long INF = std::numeric_limits::max() / 2 - 10000000; const ld pi = acos(-1); //constexpr int MOD = 1000000007; //1e9 + 7 constexpr int MOD = 998244353; // 7 * 17 * 2^23 + 1 //---------- chmax, min 関連 ---------- template inline void chmax(T& a, T b) { if (a < b) a = b; } template inline void chmin(T& a, T b) { if (a > b) a = b; } //---------- gcd, lcm ---------- template T my_gcd(T a, T b) { if (b == (T)0) return a; return my_gcd(b, a % b); } template T my_lcm(T a, T b) { return a / my_gcd(a, b) * b; } // ax + by = gcd(a, b) を解く。返り値は、gcd(a, b)。 // 但し、a, b が負である場合は、返り値が正であることは保障されない。 long long my_gcd_ext(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long tempo = my_gcd_ext(b, a % b, y, x); //bx' + ry' = gcd(a, b) → (qb + r)x + by = gcd(a, b) に戻さないといけない。// (r = a % b) //b(x' - qy') + (bq + r)y' = gcd(a, b) と同値変形できるから、 // x = y', y = x' - qy' y -= (a / b) * x; return tempo; } //中国式剰余の定理 (CRT) // x = base1 (mod m1) かつ x = base2 (mod m2) を解く。 // リターン値を (r, m) とすると解は x = r (mod m) で、m = lcm(m1, m2) // 解なしの場合は (0, -1) をリターン pair CRT(long long base1, long long m1, long long base2, long long m2) { long long p, q; long long gcd0 = my_gcd_ext(m1, m2, p, q); if ((base2 - base1) % gcd0 != 0) return make_pair(0, -1); long long lcm0 = m1 * (m2 / gcd0); // 括弧がないとオーバーフローのリスクがある。 p *= (base2 - base1) / gcd0; p %= (m2 / gcd0); //q *= (base2 - base1) / gcd0; //q %= (m1 / gcd0); long long r = (base1 + m1 * p) % lcm0; if (r < 0) r += lcm0; return make_pair(r, lcm0); } //M を法として、a の逆元を返す。但し gcd(a, M) = 1。 long long my_invmod(long long a, long long M) { long long x = 0, y = 0; long long memo = my_gcd_ext(a, M, x, y); assert(memo == 1LL); x %= M; if (x < 0) x += M; return x; } //繰り返し2乗法 (非再帰) //N^aの、Mで割った余りを求める。 template constexpr T my_pow(T N, long long a, long long M) { assert(0 <= a); T x = N % M, res = (T)1; while (a) { if (a & 1) { res *= x; res %= M; } x *= x; // x は *this の (2のべき乗) 乗を管理する。 x %= M; a >>= 1; } return res; } // 繰り返し2乗法 (非再帰) // T = modint でも動く。 template constexpr T my_pow(T N, long long a) { assert(0 <= a); T x = N, res = (T)1; while (a) { if (a & 1) res *= x; x *= x; // x は *this の (2のべき乗) 乗を管理する。 a >>= 1; } return res; } // base を底としたときの、n の i桁目を、v.at(i) に入れる。 vector ll_to_vector(signed base, long long n) { long long tempo = n; long long tempo2 = n; //桁数を求めるときに使う signed n_digit = 1; while (tempo2 >= base) { tempo2 /= base; n_digit++; } vector v(n_digit, 0); // v のサイズを適切に調整。 long long denominator = my_pow((long long)base, (long long)(n_digit - 1)); for (signed i = 0; i < n_digit; i++) { v.at(i) = tempo / denominator; tempo -= v.at(i) * denominator; denominator /= base; } return v; } // M 桁に足りない場合、0 を追加して強制的に M 桁にする。 vector ll_to_vector(signed base, long long n, int M) { vector v = ll_to_vector(base, n); //assert((int)v.size() <= M); if ((int)v.size() >= M) return v; else { int diff = M - v.size(); vector res(diff, 0); for (int i = 0; i < (int)v.size(); i++) res.emplace_back(v.at(i)); return res; } } //エラトステネスの篩で、prime で ないところに false を入れる。O(n loglog n) // T = int (defalt, sieve が ll で間に合うことはないので。) // vector に替えるとむしろ遅くなる。 template vector sieve_bool(T N) { vector res(N + 1, true); res.at(0) = false; res.at(1) = false; for (T i = 2; 2 * i <= N; i++) { res.at(2 * i) = false; } for (T i = 3; i * i <= N; i += 2) { //ここからは奇数のみ探索。i の倍数に false を入れる。 if (res.at(i)) { T j = i * i; // i^2 未満の i の倍数には、すでに false が入っているはず。 while (j <= N) { res.at(j) = false; j += 2 * i; } } } return res; }; // n + 1 の サイズの vector を返す。res.at(i) には、i の 1 以外で最小の約数を入れる。 // res.at(i) == i で、i != 0, 1 なら i は素数。 // 2e8 なら、2.3 ~ 2.4 sec 程度で終わる。sieve_bool は 0.7 sec なので、3 倍強遅い。ll にすると、3.2 sec に伸びてしまう。 // T = int (defalt, sieve が ll で間に合うことはないので。) template vector sieve(T n) { n++; // n まで判定する。配列サイズは +1。 vector res(n, 0); for (T i = 1; i < n; i++) { if (i % 2 == 0) res.at(i) = 2; // 偶数をあらかじめ処理。 else res.at(i) = i; // 奇数には自分自身を入れる。 } for (T i = 3; i * i < n; i += 2) { //ここからは奇数のみ探索。i の倍数に i を入れる。 if (res.at(i) == i) { T j = i * i; // i^2 未満の i の倍数には、すでに最小の約数が入っているはず。 while (j < n) { if (res.at(j) == j) res.at(j) = i; j += 2 * i; } } } return res; }; //O (sqrt(n)) で素数判定する用。 constexpr bool is_prime(long long N) { //有名素数 if (N == 1000000007 || N == 1000000009) return true; if (N == 998244353 || N == 167772161 || N == 469762049 || N == 1224736769) return true; //g = 3; if (N == 924844033 || N == 1012924417) return true; //g = 5; if (N == 163577857) return true; //g = 23; //小さい素数の別処理 if (N <= 1) return false; if (N == 2 || N == 3) return true; if (N % 2 == 0) return false; if (N % 3 == 0) return false; for (long long i = 1; (6 * i + 1) * (6 * i + 1) <= N; ++i) { if (N % (6 * i + 1) == 0) return false; } for (long long i = 0; (6 * i + 5) * (6 * i + 5) <= N; ++i) { if (N % (6 * i + 5) == 0) return false; } return true; } template constexpr bool is_prime_constexpr = is_prime(n); // 素因分解アルゴリズム (O(sqrt(N)) → O(N^0.25) のρ法も持っている。 // T = long long (defalt) template map PrimeFactor(T N) { map res; T i = 2; while (i * i <= N) { while (N % i == 0) { res[i]++; N /= i; } i += 1 + (i % 2); //i == 2 の場合だけ +1, その他の場合は +2 } if (N > 1) res[N]++; //sqrt((元の N)) より大きな素因数は高々1つしかない。 return res; } //関数 sieve で得た、vector min_factor を持ってるときに、素因数分解を高速で行うための関数。 // T = int (defalt, sieve が ll で間に合うことはないので。) template map PrimeFactor2(T target, vector& min_factor) { map res; if (min_factor.empty() || (T)min_factor.size() - 1 < target) min_factor = sieve(target); while (target > 1) { res[min_factor[target]]++; target /= min_factor[target]; } return res; } //約数全列挙を O(sqrt(N)) で行うための関数。 vector count_dividers(long long target) { vector dividers, tempo; long long i = 1; while (i * i < target + 1) { if (target % i == 0) { dividers.push_back(i); if (i < target / i) tempo.push_back(target / i); // if節がないと、平方数の時、sqrt(target) がダブルカウントされる。 } i++; } for (long long j = 0; j < (long long)tempo.size(); j++) { dividers.push_back(tempo.at(tempo.size() - 1 - j)); } return dividers; } //関数 sieve で得た、vector min_factor を持ってるときに、約数全列挙を高速で行うための関数。 // T = int (defalt, sieve が ll で間に合うことはないので。) template vector count_dividers2(T target, vector& min_factor, bool is_sort = false) { vector dividers = { 1 }; map memo = PrimeFactor2(target, min_factor); for (auto&& iter = memo.begin(); iter != memo.end(); iter++) { vector tempo = dividers; for (T k = 0; k < (T)tempo.size(); k++) { T times = 1; for (T j = 1; j <= (iter->second); j++) { times *= iter->first; dividers.push_back(tempo[k] * times); } } } if (is_sort) sort(dividers.begin(), dividers.end()); //sortしないと小さい順に並ばないが、必要ないなら消しても良い。 return dividers; } class UnionFind { public: vector parent; vector rank; vector v_size; UnionFind(int N) : parent(N), rank(N, 0), v_size(N, 1) { rep(i, N) { parent[i] = i; } } int root(int x) { if (parent[x] == x) return x; return parent[x] = root(parent[x]); //経路圧縮 } void unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return; //xの根とyの根が同じなので、何もしない。 if (rank[rx] < rank[ry]) { parent[rx] = ry; v_size[ry] += v_size[rx]; } else { parent[ry] = rx; v_size[rx] += v_size[ry]; if (rank[rx] == rank[ry]) rank[rx]++; } } bool same(int x, int y) { return (root(x) == root(y)); } int count_tree() { int N = parent.size(); int res = 0; rep(i, N) { if (root(i) == i) res++; } return res; } int size(int x) { return v_size[root(x)]; } }; // 幾何。二点間距離。 ld calc_dist(int x1, int y1, int x2, int y2) { int tempo = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); ld res = sqrt((ld)tempo); return res; } //ランレングス圧縮 vector> RunLength(const string& S) { int N = S.size(); vector> memo; if (N == 1) { memo.push_back(MP(1, S.at(0))); return memo; } int tempo = 1; for (int i = 1; i < N; i++) { if (i != N - 1) { if (S.at(i) == S.at(i - 1)) tempo++; else { memo.push_back(MP(tempo, S.at(i - 1))); tempo = 1; } } else { if (S.at(i) == S.at(i - 1)) { tempo++; memo.push_back(MP(tempo, S.at(i - 1))); } else { memo.push_back(MP(tempo, S.at(i - 1))); memo.push_back(MP(1, S.at(i))); } } } return memo; } void printf_ld(ld res) { printf("%.12Lf\n", res); //cout << std::fixed << std::setprecision(12) << res << endl; } template void print_vec(vector v) { int N = v.size(); rep(i, N) { if (i != N - 1) cout << v.at(i) << " "; else cout << v.at(i) << endl; } } template void print_vec(deque v) { int N = v.size(); rep(i, N) { if (i != N - 1) cout << v.at(i) << " "; else cout << v.at(i) << endl; } } //mint 構造体。自動で mod を取る。 //m はコンパイル時に決まる定数である必要があるので、入力を用いることはできない。 //割り算に m の素数判定が必要になり、is_prime に依存するようになった。 //※ constexpr 関数の const 修飾は C++11 では許されない。 template class mint { private: T _val; public: //---------- コンストラクタ ---------- constexpr mint(T v = 0LL) noexcept : _val(v% m) { if (_val < 0) _val += m; } constexpr T val() const noexcept { return _val; } //------------------------------ 二項演算子のオーバーロード ------------------------------ constexpr mint& operator += (const mint& r) noexcept { _val += r._val; if (_val >= m) _val -= m; return *this; } constexpr mint& operator -= (const mint& r) noexcept { _val -= r._val; if (_val < 0) _val += m; return *this; } constexpr mint& operator *= (const mint& r) noexcept { _val *= r._val; _val %= m; return *this; } constexpr mint& operator /= (const mint& r) noexcept { if (!prime) { //a * u + b * v = 1 を互除法で解く。但し、gcd(a, m) == 1 でなければならない。 T a = r._val, b = m, u = 1, v = 0; while (b) { T q = a / b; a -= q * b; swap(a, b); //互除法。余りをとって swap。 u -= q * v; swap(u, v); } //assert(a == 1); //gcd(r._val, m) == 1; _val *= u; _val %= m; if (_val < 0) _val += m; } else { //フェルマーの小定理。底が prime である場合のみ使用可能。 *this *= r.modpow(m - 2); } return *this; } constexpr mint operator + (const mint& r) const noexcept { return mint(*this) += r; } constexpr mint operator - (const mint& r) const noexcept { return mint(*this) -= r; } constexpr mint operator * (const mint& r) const noexcept { return mint(*this) *= r; } constexpr mint operator / (const mint& r) const noexcept { return mint(*this) /= r; } constexpr bool operator == (const mint& r) const noexcept { return this->_val == r._val; } constexpr bool operator != (const mint& r) const noexcept { return this->_val != r._val; } //------------------------------ 単項演算子のオーバーロード ------------------------------ //---------- 前置インクリメントのオーバーロード ---------- constexpr mint operator ++() noexcept { this->_val++; if (this->_val == m) this->_val = 0; return mint(*this); } constexpr mint operator --() noexcept { if (this->_val == 0) this->_val = m; this->_val--; return mint(*this); } //---------- 後置インクリメントのオーバーロード ---------- constexpr mint operator++(signed) noexcept { mint temp(_val); ++_val; if (_val == m) _val = 0; return temp; } constexpr mint operator--(signed) noexcept { mint temp(_val); if (_val == 0) _val = m; --_val; return temp; } constexpr mint operator -() const noexcept { return mint(-_val); } //---------- 入出力のオーバーロード ---------- friend constexpr ostream& operator << (ostream& os, const mint& x) noexcept { return os << x._val; } friend istream& operator >> (istream& is, mint& x) noexcept { T init_val; is >> init_val; x = mint(init_val); return is; } //---------- 逆元 ---------- constexpr mint inverse() const noexcept { mint e(1); return e / (*this); } private: // 愚直な O(sqrt(m)) の素数判定; 余りに m が大きすぎると、コンパイル時の定数式の評価に失敗するが、1e11 程度までなら大丈夫。 // Miller-Rabin を使ってもよい。 static constexpr bool prime = is_prime_constexpr; //---------- 繰り返し二乗法 ---------- constexpr mint modpow(long long n) const noexcept { assert(0 <= n); mint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; // x は *this の (2のべき乗) 乗を管理する。 n >>= 1; } return r; } }; using modint = mint; vector dp_fac; vector dp_fac_inv; // x!まで計算するときに最初に呼び出す。o(x). template void fac_initialize(int x, vector& dp = dp_fac, vector& dp_inv = dp_fac_inv) { if ((int)dp.size() <= x) { int n = dp.size(); if (n == 0) ++n; dp.resize(x + 1, (T)1); for (int i = n; i <= x; ++i) { dp.at(i) = dp.at(i - 1) * i; } } if ((int)dp_inv.size() <= x) { int n = dp_inv.size(); dp_inv.resize(x + 1, (T)1); dp_inv.at(x) /= dp.at(x); for (int i = x - 1; i >= n; --i) { dp_inv.at(i) = dp_inv.at(i + 1) * (i + 1); } } } // 階乗。x ! まで計算する。結果は dp (デフォルトで dp_fac) に保存する。 // long long にするためには、第二引数に vector を指定する必要がある。20 ! = 2.43e18 まで long long に入る。 template T factorial(int x, vector& dp = dp_fac) { assert(x >= 0); //既に計算済み if ((int)dp.size() > x) { return dp.at(x); } int n = dp.size(); //dp サイズを x + 1 に伸ばす。 for (int i = n; i < x + 1; i++) { if (i == 0) dp.push_back((T)1); else dp.push_back(dp.back() * i); } return dp.at(x); } template T factorial_inv(int x, vector& dp = dp_fac_inv) { assert(x >= 0); //既に計算済み if ((int)dp.size() > x) { return dp.at(x); } int n = dp.size(); //dp サイズを x + 1 に伸ばす。 for (int i = n; i < x + 1; i++) { if (i == 0) dp.push_back((T)1); else dp.push_back(dp.back() / i); } return dp.at(x); } // 二項係数 N_C_a template T my_comb(U N, U a, vector& dp = dp_fac, vector& dp_inv = dp_fac_inv) { if (N < a) return (T)0; T ans = factorial(N, dp); ans *= factorial_inv(a, dp_inv); ans *= factorial_inv(N - a, dp_inv); return ans; } //二項係数 N_C_a (1点計算用) template T my_comb2(U N, U a) { if (N < a) return (T)0; T answer = 1; for (U i = (U)0; i < a; i++) { answer *= (N - i); answer /= i + 1; } return answer; } ld now_clock() { ld t = (ld)clock() / (ld)CLOCKS_PER_SEC; return t; } //四近傍 const vector vdh = { 1, -1, 0, 0 }; const vector vdw = { 0, 0, 1, -1 }; // グラフ構造体 (辺の重みあり) // add_edge, add_biedge (有向辺、無向辺の追加) // bfs01, dijkstra (最短路) の機能 // route (最短経路を求める) 機能 // cnt_route (最短路が何通りあるか求める) 機能 → ABC 021 C - 正直者の高橋くん // from_grid(const vector& S); grid からの変換 // Kruskal (UnionFind に依存), Prim 法での最小全域木 (MST) のコスト。(無向グラフの場合のみ) // bfsTopSort (トポロジカルソート) // IsClosed() 閉路の有無を判定し、閉路がある場合はその 1つを返す。(無向グラフの場合のみ) // bfs_tree(int root), dfs_tree(int root) bfs木とdfs木を返す。(無向グラフの場合のみ) template struct edge { int to; T weight; int index; //何番目の辺か。 constexpr bool operator < (const edge& r) const noexcept { if (weight != r.weight) return (weight < r.weight); else return (index < r.index); } constexpr bool operator > (const edge& r) const noexcept { if (weight != r.weight) return (weight > r.weight); else return (index > r.index); } }; template bool operator== (const edge& a, const edge& b) { return (a.to == b.to && a.weight == b.weight && a.index == b.index); }; template struct edge2 { int from; int to; T weight; constexpr bool operator < (const edge2& r) const noexcept { if (weight != r.weight) return (weight < r.weight); else return (from < r.from); } }; template class graph { int sp = -1; // 始点 public: vector>> G; vector> edges; vector dist; // 始点からの距離 vector prev; // 始点から最短距離で進む際の直前の頂点 vector prev_edge; // 始点から最短距離で進む際の直前の辺 graph(int _n) : N(_n) { initialize(_n); }; graph() : N(0) {}; // G に対して、有向辺を加える。 void add_edge(int from, int to, T weight = (T)1) { assert(0 <= from && from < N); assert(0 <= to && to < N); assert((T)0 <= weight); G.at(from).emplace_back(edge{ to, weight, (int)edges.size() }); edges.push_back(edge2{from, to, weight}); } // G に対して、無向辺を加える。 void add_biedge(int from, int to, T weight = (T)1) { add_edge(from, to, weight); add_edge(to, from, weight); } // 最短路 (01-BFS / weight が 0 or 1 のみの場合使える / 複数始点) void bfs01(vector vs) { const T ini_dist = -1; //assert(!vs.empty()); deque que; dist.assign(N, ini_dist); prev.assign(N, -1); prev_edge.assign(N, -1); for (auto&& s : vs) { assert(0 <= s && s < N); que.push_front(s); dist.at(s) = 0; } while (!que.empty()) { int v = que.front(); que.pop_front(); for (edge e : G.at(v)) { int nextv = e.to; //if の 第二項が無いと、本当はcost = 0 で行けるのに、先に cost = 1 の辺を発見した場合バグる。 if (dist.at(nextv) != ini_dist && dist.at(nextv) <= dist.at(v) + e.weight) continue; dist.at(nextv) = dist.at(v) + e.weight; if ((int)vs.size() == 1) { prev.at(nextv) = v; prev_edge.at(nextv) = e.index; } if (e.weight) que.push_back(nextv); else que.push_front(nextv); } } } // 最短路 (01-BFS / weight が 0 or 1 のみの場合使える / 単一始点) void bfs01(int s) { vector vs = { s }; sp = s; bfs01(vs); } //最短路 dijkstra (経路復元あり, 直前の頂点を prev, 直前の辺を prev_edge に入れる。) void dijkstra(int s) { assert(0 <= s && s < N); sp = s; dist.assign(N, INF); prev.assign(N, -1); prev_edge.assign(N, -1); //first が最短距離、second が頂点番号。 priority_queue, vector>, greater>> que; dist.at(s) = (T)0; que.push(make_pair((T)0, s)); while (!que.empty()) { pair p = que.top(); que.pop(); int v = p.second; if (dist.at(v) < p.first) continue; //最短距離がすでに更新されているので無視。 for (int i = 0; i < (int)G.at(v).size(); i++) { edge e = G.at(v).at(i); if (dist.at(e.to) > dist.at(v) + e.weight) { dist.at(e.to) = dist.at(v) + e.weight; prev.at(e.to) = v; prev_edge.at(e.to) = e.index; que.push(make_pair(dist.at(e.to), e.to)); } } } } // 始点 sp からの距離 dist が求まっている際に、sp から 頂点 v への経路を返す。 // first 通る頂点番号, second 通る辺番号 // sp から v にたどりつけない場合バグる。 pair, vector> route(int v) { assert(sp != -1); vector res = { v }; // 頂点番号 vector es; while (res.back() != sp) { int now = res.back(); int next_v = prev.at(now); res.push_back(next_v); es.push_back(prev_edge.at(now)); } reverse(res.begin(), res.end()); return { res, es }; } // 始点 sp からの距離 dist が求まっている際に、 // 始点 sp から頂点 i までの最短距離での行き方を求める。 template U cnt_route(int i, vector& cnt, vector& seen) { assert(sp != -1); assert((int)cnt.size() == N); assert((int)seen.size() == N); if (seen.at(i)) return cnt.at(i); else if (i == sp) { seen.at(i) = true; return cnt.at(i) = (U)1; } else { U sum = 0; for (auto& e : G.at(i)) { int nextv = e.to; if (dist.at(i) == dist.at(nextv) + e.weight) { sum += cnt_route(nextv, cnt, seen); } } seen.at(i) = true; return cnt.at(i) = sum; } } // grid から隣接グラフを構築。 void from_grid(const vector& S) { assert(!S.empty()); int H = S.size(); int W = S.at(0).size(); int N = H * W; initialize(N); for (int h = 0; h < H; ++h) { for (int w = 0; w < W; ++w) { for (int i = 0; i < (int)vdh.size(); ++i) { int dh = vdh.at(i), dw = vdw.at(i); if (h + dh < 0 || H <= h + dh) continue; if (w + dw < 0 || W <= w + dw) continue; int v = h * W + w; int nextv = (h + dh) * W + (w + dw); if (S.at(h + dh).at(w + dw) == '#') { //壁 continue; } else { add_edge(v, nextv, 1); } } } } } // (無向グラフの場合のみ) //---------- Prim 法によって、最小全域木 (MST, Minimum Spanning Tree) 問題を解く ---------- // sp を含む連結成分の最小全域木のコストと、その頂点数 (元グラフが連結なら N になる) の pair を返す。 template pair Prim(int sp = 0) { assert(0 <= sp && sp < N); U sum = 0; int marked_cnt = 0; vector marked(N, false); priority_queue, vector>, greater>> que; // ----- ↓初期頂点の処理↓ ----- ++marked_cnt; marked[sp] = true; for (auto&& e : G[sp]) que.push(e); // ----- ↑初期頂点の処理↑ ----- while (marked_cnt < N && !que.empty()) { auto e = que.top(); que.pop(); int nextv = e.to; if (marked[nextv]) continue; ++marked_cnt; marked[nextv] = true; for (auto&& nexte : G[nextv]) que.push(nexte); sum += e.weight; } return make_pair(sum, marked_cnt); } // (無向グラフの場合のみ) //---------- Kruskal 法によって、最小全域木 (MST, Minimum Spanning Tree) 問題を解く ---------- //---------- UnionFindも必要 ---------- // first: 最小全域木のコストを返す。連結でなければ INF を返す。 // second: 最小全域木に含まれる全ての辺 (連結でなければ空) template pair>> Kruskal() { assert(edges.size() % 2 == 0); int E = edges.size() / 2; vector> es; for (int i = 0; i < (int)edges.size(); i += 2) { int v1 = edges.at(i).from; int v2 = edges.at(i).to; T w = edges.at(i).weight; assert(edges.at(i + 1).from == v2); assert(edges.at(i + 1).to == v1); assert(edges.at(i + 1).weight == w); es.push_back(edge2{v1, v2, w}); } std::sort(es.begin(), es.end()); U sum = 0; vector> vres; UnionFind tree(N); rep(i, E) { edge2 e = es.at(i); if (!tree.same(e.from, e.to)) { tree.unite(e.from, e.to); sum += e.weight; vres.push_back(e); } } // そもそも連結グラフだったか判定。 rep(v, N) { if (!tree.same(0, v)) return { INF, vector>(0) }; } return { sum, vres }; } // 返り値.first; トポロジカルソート可能か否か。 // 返り値.second; トポロジカルソート可能な場合の一例。 pair> bfsTopSort() { vector CntIn(N, 0); for (int i = 0; i < N; ++i) { for (int j = 0; j < (int)G.at(i).size(); ++j) { int v = G.at(i).at(j).to; ++CntIn.at(v); } } vector res; queue que; //priority_queue, greater> que; //辞書順になる。 for (int i = 0; i < N; ++i) { if (CntIn.at(i) == 0) { que.push(i); --CntIn.at(i); } } while (!que.empty()) { int v = que.front(); que.pop(); //int v = que.top(); que.pop(); //priority_que の場合 res.push_back(v); for (int i = 0; i < (int)G.at(v).size(); ++i) { int next_v = G.at(v).at(i).to; if (CntIn.at(next_v) == -1) { //トポロジカルソート失敗。 return make_pair(false, vector()); } --CntIn.at(next_v); if (CntIn.at(next_v) == 0) { que.push(next_v); } } } if (res.size() == N) { return make_pair(true, res); } else { return make_pair(false, vector()); } } //閉路検出を行う。(無向グラフの場合) //first; 閉路があるか否かの bool //second; 閉路がある場合の一つの例。 pair> IsClosed() { vector seen(N, false); for (int v = 0; v < N; ++v) { if (seen.at(v)) continue; vector vec; bool flag = dfs_closed(v, -1, vec, seen); if (flag) { vector res; while (!vec.empty()) { res.push_back(vec.back()); vec.pop_back(); if (res.size() > 1 && res.front() == res.back()) break; } assert((int)res.size() > 1); return make_pair(true, res); } } vector vec; return make_pair(false, vec); } //bfs木を返す (無向辺の場合のみ)。含まれない辺は、この木において祖先と子孫の関係にない。 vector> bfs_tree(int root = 0) { assert(0 <= root && root < N); vector> res; //含まれる辺の両端の頂点 vector edge_index; //含まれる辺の番号 queue que; que.push(root); UnionFind uf(N); while (!que.empty()) { int v = que.front(); que.pop(); for (const auto& e : G.at(v)) { int nv = e.to; if (uf.same(root, nv)) continue; uf.unite(root, nv); que.push(nv); res.push_back({ v, nv }); edge_index.push_back(e.index); } } // 辺番号 (出力はしない) for (int i = 0; i < (int)edge_index.size(); ++i) edge_index.at(i) /= 2; //sort(ALL(edge_index)); //print_vec(edge_index); return res; } //dfs木を返す (無向辺の場合のみ)。含まれない辺は、この木において必ず祖先と子孫の関係にある。 //さらに、lowlink を計算し、橋の判定を行えるようにする。 //言い換えれば、全ての cross edge がこの木に含まれる。 vector> dfs_tree(int root = 0) { assert(0 <= root && root < N); vector> res; //含まれる辺の両端の頂点 vector edge_index; //含まれる辺の番号 vector seen_v(N, false); vector seen_e((int)edges.size(), false); ord.assign(N, -1); //訪問順序 lowlink.assign(N, -1); int first_ptr = 0; dfs_tree_func(root, res, edge_index, seen_v, seen_e, first_ptr); // 辺番号 (出力はしない) for (int i = 0; i < (int)edge_index.size(); ++i) edge_index.at(i) /= 2; //sort(ALL(edge_index)); //print_vec(edge_index); return res; } //dfs木を構築した後、辺が橋か否か判定できる。 bool IsBridge(int from, int to) { //dfs実行後である確認。 assert(!ord.empty() && ord[0] != -1); assert(0 <= from && from < N); assert(0 <= to && to < N); if (ord[from] > ord[to]) swap(from, to); if (ord[from] < lowlink[to]) return true; else return false; } private: int N; vector ord; //dfs木での訪問順。lowlink を求めるときに使う。 vector lowlink; // 初期化 void initialize(int n) { G.assign(n, vector>()); sp = -1; dist.assign(n, INF); prev.assign(n, -1); prev_edge.assign(n, -1); } //閉路検出に使う dfs (無向グラフの場合) bool dfs_closed(int v, int from, vector& vec, vector& seen) { vec.push_back(v); if (seen.at(v)) return true; else seen.at(v) = true; for (auto&& ed : G.at(v)) { int next_v = ed.to; if (next_v == from) continue; bool flag = dfs_closed(next_v, v, vec, seen); if (flag) return true; } vec.pop_back(); return false; } //dfs木構築に使うdfs (無向グラフの場合) //res, edge_index は dfs木の辺の両端の頂点番号, 辺番号。 //first_ptr は訪問順序のカウント。 void dfs_tree_func(int v, vector>& res, vector& edge_index, vector& seen_v, vector& seen_e, int& first_ptr) { seen_v[v] = true; //行きがけ順 ord[v] = lowlink[v] = first_ptr++; for (const auto& e : G[v]) { seen_e[e.index] = true; int nv = e.to; if (!seen_v[nv]) { res.push_back({ v, nv }); edge_index.push_back(e.index); dfs_tree_func(nv, res, edge_index, seen_v, seen_e, first_ptr); chmin(lowlink[v], lowlink[nv]); } else { //行先の頂点を既に見ている、かつ逆辺を見ていない。v → nv は後退辺 (backward edge) if (!seen_e[e.index % 2 == 0 ? e.index + 1 : e.index - 1]) { chmin(lowlink[v], ord[nv]); } } } } }; //https://ei1333.github.io/algorithm/namori.html //なもりグラフ。graph を継承する。 template class Namori : public graph { public: Namori(int _n) : graph(_n) {}; Namori() : graph(0) {}; //橋でない辺 (つまり閉路内の辺) を全て取り除いて、なもりグラフを木に分解する。 void decomposition() { vector cnt_from(this->G.size()); for (int i = 0; i < (int)this->G.size(); ++i) { cnt_from[i] = this->G[i].size(); } forest.resize(this->G.size()); queue que; vector seen((int)this->G.size(), false); for (int i = 0; i < (int)this->G.size(); ++i) { if (cnt_from[i] == 1) { que.push(i); seen[i] = true; } } while (!que.empty()) { int v = que.front(); que.pop(); for (auto&& ne : this->G[v]) { int nv = ne.to; if (seen[nv]) continue; --cnt_from[nv]; forest[v].push_back(nv); forest[nv].push_back(v); if (cnt_from[nv] > 1) continue; que.push(nv); seen[nv] = true; } } //ここで seen が true でない頂点は、全てループ内。 for (int v = 0; v < (int)this->G.size(); ++v) { if (seen[v]) continue; dfs_loop(v, seen); break; } //ループ内の頂点を根として、木がどの根から生えているか。 v_root.assign((int)this->G.size(), -1); for (auto& v0 : loop) { v_root[v0] = v0; que.push(v0); while (!que.empty()) { int v = que.front(); que.pop(); for (int nv : forest[v]) { if (v_root[nv] != -1) continue; v_root[nv] = v_root[v]; que.push(nv); } } } } int root(int v) const{ assert(0 <= v && v < (int)this->G.size()); return v_root[v]; } bool same(int v1, int v2) const{ return (root(v1) == root(v2)); } private: vector loop; vector > forest; vector v_root; void dfs_loop(int v, vector& seen) { seen[v] = true; loop.push_back(v); for (auto&& ne : this->G[v]) { int nv = ne.to; if (seen[nv]) continue; dfs_loop(nv, seen); } }; }; signed main() { int N; cin >> N; Namori G(N); vector a(N), b(N); rep(i, N) { cin >> a[i] >> b[i]; --a[i]; --b[i]; G.add_biedge(a[i], b[i]); } G.decomposition(); vector res; rep(i, N) { if (!G.same(a[i], b[i])) res.push_back(i + 1); } cout << res.size() << endl; print_vec(res); }