結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2022-08-30 00:33:08 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 35,625 bytes |
コンパイル時間 | 17,856 ms |
コンパイル使用メモリ | 320,472 KB |
最終ジャッジ日時 | 2025-02-06 23:45:40 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include "bits/stdc++.h"#ifdef _MSC_VER#include <intrin.h> //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 <atcoder/all>//using namespace atcoder;using namespace std;//---------- 多倍長関連 ----------//#include <boost/multiprecision/cpp_int.hpp>//#include <boost/multiprecision/cpp_dec_float.hpp>//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<int, int>#define MP make_pair#define PB push_back#define ALL(v) v.begin(), v.end()constexpr int INF2 = std::numeric_limits<int>::max() / 2 - 10000000;constexpr long long INF = std::numeric_limits<long long>::max() / 2 - 10000000;const ld pi = acos(-1);//constexpr int MOD = 1000000007; //1e9 + 7constexpr int MOD = 998244353; // 7 * 17 * 2^23 + 1//---------- chmax, min 関連 ----------template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}//---------- gcd, lcm ----------template<typename T = long long>T my_gcd(T a, T b) {if (b == (T)0) return a;return my_gcd<T>(b, a % b);}template<typename T = long long>T my_lcm(T a, T b) {return a / my_gcd<T>(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<long long, long long> 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<typename T = long long>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<typename T = long long>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<signed> 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<signed> v(n_digit, 0); // v のサイズを適切に調整。long long denominator = my_pow<long long>((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<signed> ll_to_vector(signed base, long long n, int M) {vector<signed> 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<signed> 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<char> に替えるとむしろ遅くなる。template<typename T = int>vector<bool> sieve_bool(T N) {vector<bool> 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<typename T = int>vector<T> sieve(T n) {n++; // n まで判定する。配列サイズは +1。vector<T> 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 <int n> constexpr bool is_prime_constexpr = is_prime(n);// 素因分解アルゴリズム (O(sqrt(N)) → O(N^0.25) のρ法も持っている。// T = long long (defalt)template<typename T = long long>map<T, T> PrimeFactor(T N) {map<T, T> 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<typename T = int>map<T, T> PrimeFactor2(T target, vector<T>& min_factor) {map<T, T> res;if (min_factor.empty() || (T)min_factor.size() - 1 < target) min_factor = sieve<T>(target);while (target > 1) {res[min_factor[target]]++;target /= min_factor[target];}return res;}//約数全列挙を O(sqrt(N)) で行うための関数。vector<long long> count_dividers(long long target) {vector <long long> 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<typename T = int>vector<T> count_dividers2(T target, vector<T>& min_factor, bool is_sort = false) {vector<T> dividers = { 1 };map<T, T> memo = PrimeFactor2<T>(target, min_factor);for (auto&& iter = memo.begin(); iter != memo.end(); iter++) {vector <T> 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<int> parent;vector<int> rank;vector<int> 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<pair<int, char>> RunLength(const string& S) {int N = S.size();vector<pair<int, char>> 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<typename T = long long>void print_vec(vector<T> v) {int N = v.size();rep(i, N) {if (i != N - 1) cout << v.at(i) << " ";else cout << v.at(i) << endl;}}template<typename T = long long>void print_vec(deque<T> 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<int m, typename T = long long> 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<m, T>& x) noexcept {return os << x._val;}friend istream& operator >> (istream& is, mint<m, T>& x) noexcept {T init_val;is >> init_val;x = mint<m, T>(init_val);return is;}//---------- 逆元 ----------constexpr mint<m, T> inverse() const noexcept {mint<m, T> e(1);return e / (*this);}private:// 愚直な O(sqrt(m)) の素数判定; 余りに m が大きすぎると、コンパイル時の定数式の評価に失敗するが、1e11 程度までなら大丈夫。// Miller-Rabin を使ってもよい。static constexpr bool prime = is_prime_constexpr<m>;//---------- 繰り返し二乗法 ----------constexpr mint<m, T> modpow(long long n) const noexcept {assert(0 <= n);mint<m, T> x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x; // x は *this の (2のべき乗) 乗を管理する。n >>= 1;}return r;}};using modint = mint<MOD, long long>;vector<modint> dp_fac;vector<modint> dp_fac_inv;// x!まで計算するときに最初に呼び出す。o(x).template<typename T = modint>void fac_initialize(int x, vector<T>& dp = dp_fac, vector<T>& 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<modint>) に保存する。// long long にするためには、第二引数に vector<long long> を指定する必要がある。20 ! = 2.43e18 まで long long に入る。template<typename T = modint>T factorial(int x, vector<T>& 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<typename T = modint>T factorial_inv(int x, vector<T>& 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_atemplate<typename T = modint, typename U = int>T my_comb(U N, U a, vector<T>& dp = dp_fac, vector<T>& dp_inv = dp_fac_inv) {if (N < a) return (T)0;T ans = factorial<T>(N, dp);ans *= factorial_inv<T>(a, dp_inv);ans *= factorial_inv<T>(N - a, dp_inv);return ans;}//二項係数 N_C_a (1点計算用)template<typename T, typename U = int>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<int> vdh = { 1, -1, 0, 0 };const vector<int> vdw = { 0, 0, 1, -1 };// グラフ構造体 (辺の重みあり)// add_edge, add_biedge (有向辺、無向辺の追加)// bfs01, dijkstra (最短路) の機能// route (最短経路を求める) 機能// cnt_route (最短路が何通りあるか求める) 機能 → ABC 021 C - 正直者の高橋くん// from_grid(const vector<string>& S); grid からの変換// Kruskal (UnionFind に依存), Prim 法での最小全域木 (MST) のコスト。(無向グラフの場合のみ)// bfsTopSort (トポロジカルソート)// IsClosed() 閉路の有無を判定し、閉路がある場合はその 1つを返す。(無向グラフの場合のみ)// bfs_tree(int root), dfs_tree(int root) bfs木とdfs木を返す。(無向グラフの場合のみ)template<typename T = long long>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<typename T> bool operator== (const edge<T>& a, const edge<T>& b) { return (a.to == b.to && a.weight == b.weight && a.index == b.index); };template<typename T = long long>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<typename T = long long>class graph {int sp = -1; // 始点public:vector<vector<edge<T>>> G;vector<edge2<T>> edges;vector<T> dist; // 始点からの距離vector<int> prev; // 始点から最短距離で進む際の直前の頂点vector<int> 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<T>{ to, weight, (int)edges.size() });edges.push_back(edge2<T>{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<int> vs) {const T ini_dist = -1;//assert(!vs.empty());deque<int> 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<T> 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<int> 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<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> que;dist.at(s) = (T)0; que.push(make_pair((T)0, s));while (!que.empty()) {pair<T, int> 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<T> 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<int>, vector<int>> route(int v) {assert(sp != -1);vector<int> res = { v }; // 頂点番号vector<int> 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<typename U = modint>U cnt_route(int i, vector<U>& cnt, vector<bool>& 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<string>& 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<typename U = T>pair<U, int> Prim(int sp = 0) {assert(0 <= sp && sp < N);U sum = 0;int marked_cnt = 0;vector<bool> marked(N, false);priority_queue<edge<T>, vector<edge<T>>, greater<edge<T>>> 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<typename U = T>pair<U, vector<edge2<T>>> Kruskal() {assert(edges.size() % 2 == 0);int E = edges.size() / 2;vector<edge2<T>> 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<T>{v1, v2, w});}std::sort(es.begin(), es.end());U sum = 0;vector<edge2<T>> vres;UnionFind tree(N);rep(i, E) {edge2<T> 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<edge2<T>>(0) };}return { sum, vres };}// 返り値.first; トポロジカルソート可能か否か。// 返り値.second; トポロジカルソート可能な場合の一例。pair<bool, vector<int>> bfsTopSort() {vector<int> 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<int> res;queue<int> que;//priority_queue<int, vector<int>, greater<int>> 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<int>());}--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<int>());}}//閉路検出を行う。(無向グラフの場合)//first; 閉路があるか否かの bool//second; 閉路がある場合の一つの例。pair<bool, vector<int>> IsClosed() {vector<bool> seen(N, false);for (int v = 0; v < N; ++v) {if (seen.at(v)) continue;vector<int> vec;bool flag = dfs_closed(v, -1, vec, seen);if (flag) {vector<int> 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<int> vec;return make_pair(false, vec);}//bfs木を返す (無向辺の場合のみ)。含まれない辺は、この木において祖先と子孫の関係にない。vector<pair<int, int>> bfs_tree(int root = 0) {assert(0 <= root && root < N);vector<pair<int, int>> res; //含まれる辺の両端の頂点vector<int> edge_index; //含まれる辺の番号queue<int> 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<pair<int, int>> dfs_tree(int root = 0) {assert(0 <= root && root < N);vector<pair<int, int>> res; //含まれる辺の両端の頂点vector<int> edge_index; //含まれる辺の番号vector<bool> seen_v(N, false);vector<bool> 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<int> ord; //dfs木での訪問順。lowlink を求めるときに使う。vector<int> lowlink;// 初期化void initialize(int n) {G.assign(n, vector<edge<T>>());sp = -1;dist.assign(n, INF);prev.assign(n, -1);prev_edge.assign(n, -1);}//閉路検出に使う dfs (無向グラフの場合)bool dfs_closed(int v, int from, vector<int>& vec, vector<bool>& 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<pair<int, int>>& res, vector<int>& edge_index, vector<bool>& seen_v, vector<bool>& 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<typename T = long long>class Namori : public graph<T> {public:Namori(int _n) : graph<T>(_n) {};Namori() : graph<T>(0) {};//橋でない辺 (つまり閉路内の辺) を全て取り除いて、なもりグラフを木に分解する。void decomposition() {vector<int> 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<int> que;vector<bool> 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<int> loop;vector<vector<int> > forest;vector<int> v_root;void dfs_loop(int v, vector<bool>& 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<int> G(N);vector<int> 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<int> res;rep(i, N) {if (!G.same(a[i], b[i])) res.push_back(i + 1);}cout << res.size() << endl;print_vec(res);}