結果

問題 No.1254 補強への架け橋
ユーザー marurunn11
提出日時 2022-08-29 02:36:32
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 35,198 bytes
コンパイル時間 15,196 ms
コンパイル使用メモリ 321,652 KB
最終ジャッジ日時 2025-02-06 23:25:30
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 + 7
constexpr 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_a 
template<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>& loop, vector<vector<int> >& forest) {
        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;
            seen[v] = true;
            dfs_loop(v, seen);
            break;
        }
    }
private:
    void dfs_loop(int v, vector<bool>& seen) {
        for (auto&& ne : this->G[v]) {
            int nv = ne.to;
            if (seen[nv]) continue;
            seen[nv] = true;
            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]);
    }
    vector<int> loop;
    vector<vector<int>> forest;
    G.decomposition(loop, forest);
    UnionFind uf(N);
    rep(v, N) {
        for (auto nv : forest[v]) {
            uf.unite(v, nv);
        }
    }
    vector<int> res;
    rep(i, N) {
        if (!uf.same(a[i], b[i])) res.push_back(i + 1);
    }
    cout << res.size() << endl;
    print_vec(res);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0