#793995 (C++17) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	marurunn11
提出日時	2022-08-30 00:33:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	159 ms / 2,000 ms
コード長	35,625 bytes
コンパイル時間	5,320 ms
コンパイル使用メモリ	259,180 KB
実行使用メモリ	30,020 KB
最終ジャッジ日時	2024-11-15 02:41:35
合計ジャッジ時間	17,606 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	3 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	2 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	2 ms 5,248 KB
testcase_39	AC	2 ms 5,248 KB
testcase_40	AC	2 ms 5,248 KB
testcase_41	AC	2 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	3 ms 5,248 KB
testcase_44	AC	2 ms 5,248 KB
testcase_45	AC	3 ms 5,248 KB
testcase_46	AC	3 ms 5,248 KB
testcase_47	AC	3 ms 5,248 KB
testcase_48	AC	3 ms 5,248 KB
testcase_49	AC	3 ms 5,248 KB
testcase_50	AC	3 ms 5,248 KB
testcase_51	AC	3 ms 5,248 KB
testcase_52	AC	3 ms 5,248 KB
testcase_53	AC	2 ms 5,248 KB
testcase_54	AC	2 ms 5,248 KB
testcase_55	AC	3 ms 5,248 KB
testcase_56	AC	2 ms 5,248 KB
testcase_57	AC	3 ms 5,248 KB
testcase_58	AC	3 ms 5,248 KB
testcase_59	AC	2 ms 5,248 KB
testcase_60	AC	3 ms 5,248 KB
testcase_61	AC	3 ms 5,248 KB
testcase_62	AC	2 ms 5,248 KB
testcase_63	AC	13 ms 5,840 KB
testcase_64	AC	5 ms 5,248 KB
testcase_65	AC	8 ms 5,248 KB
testcase_66	AC	7 ms 5,248 KB
testcase_67	AC	4 ms 5,248 KB
testcase_68	AC	8 ms 5,248 KB
testcase_69	AC	9 ms 5,248 KB
testcase_70	AC	5 ms 5,248 KB
testcase_71	AC	5 ms 5,248 KB
testcase_72	AC	10 ms 5,248 KB
testcase_73	AC	5 ms 5,248 KB
testcase_74	AC	9 ms 5,248 KB
testcase_75	AC	8 ms 5,248 KB
testcase_76	AC	3 ms 5,248 KB
testcase_77	AC	6 ms 5,248 KB
testcase_78	AC	12 ms 5,520 KB
testcase_79	AC	12 ms 5,792 KB
testcase_80	AC	10 ms 5,376 KB
testcase_81	AC	12 ms 5,668 KB
testcase_82	AC	11 ms 5,492 KB
testcase_83	AC	143 ms 27,348 KB
testcase_84	AC	147 ms 26,528 KB
testcase_85	AC	85 ms 17,792 KB
testcase_86	AC	123 ms 23,496 KB
testcase_87	AC	137 ms 25,344 KB
testcase_88	AC	18 ms 7,000 KB
testcase_89	AC	159 ms 27,152 KB
testcase_90	AC	83 ms 18,612 KB
testcase_91	AC	67 ms 15,436 KB
testcase_92	AC	33 ms 9,780 KB
testcase_93	AC	119 ms 22,348 KB
testcase_94	AC	101 ms 20,644 KB
testcase_95	AC	105 ms 20,628 KB
testcase_96	AC	154 ms 25,856 KB
testcase_97	AC	57 ms 13,600 KB
testcase_98	AC	146 ms 26,040 KB
testcase_99	AC	79 ms 17,280 KB
testcase_100	AC	145 ms 27,828 KB
testcase_101	AC	29 ms 9,100 KB
testcase_102	AC	15 ms 6,480 KB
testcase_103	AC	32 ms 9,768 KB
testcase_104	AC	47 ms 12,068 KB
testcase_105	AC	115 ms 22,352 KB
testcase_106	AC	62 ms 14,864 KB
testcase_107	AC	147 ms 27,076 KB
testcase_108	AC	151 ms 26,956 KB
testcase_109	AC	123 ms 22,280 KB
testcase_110	AC	107 ms 20,472 KB
testcase_111	AC	118 ms 21,516 KB
testcase_112	AC	46 ms 11,620 KB
testcase_113	AC	102 ms 19,964 KB
testcase_114	AC	61 ms 14,260 KB
testcase_115	AC	20 ms 7,212 KB
testcase_116	AC	70 ms 15,952 KB
testcase_117	AC	46 ms 11,580 KB
testcase_118	AC	141 ms 25,816 KB
testcase_119	AC	75 ms 17,108 KB
testcase_120	AC	129 ms 24,996 KB
testcase_121	AC	37 ms 10,440 KB
testcase_122	AC	67 ms 15,880 KB
testcase_123	AC	2 ms 5,248 KB
testcase_124	AC	151 ms 30,020 KB
testcase_125	AC	143 ms 29,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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> 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);
}

yukicoder

結果

テストケース

ソースコード