#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include "bits/stdc++.h" #ifdef _MSC_VER #include //gcc上ではこれがあると動かない。__popcnt, umul128 等用のincludeファイル。 #define __builtin_popcount __popcnt #define __builtin_popcountll __popcnt64 #pragma warning(disable : 4996) #pragma intrinsic(_umul128) #endif //#include //using namespace atcoder; //#include //#include using namespace std; typedef long long ll; typedef long double ld; #define int long long #define double long double #define LL128 boost::multiprecision::int128_t #define LL boost::multiprecision::cpp_int #define LD100 boost::multiprecision::cpp_dec_float_100 #define rep(i, n) for(long long i = 0; i < (n); i++) #define sqrt(d) pow((ld) (d), 0.50) #define PII pair #define MP make_pair #define PB push_back #define ALL(v) v.begin(), v.end() const int INF = std::numeric_limits::max() / 2 - 100000000; const long long INF2 = std::numeric_limits::max() / 2 - 100000000; const ld pi = acos(-1); constexpr int MOD = 1000000007; //1e9 + 7 //constexpr int MOD = 1000000009; //1e9 + 9 //constexpr int MOD = 998244353; // 7 * 17 * 2^23 + 1 //無向グラフ、メモリ節約版 class Lowlink { private: struct edge { int to; int rev; bool seen; }; int N = 0; vector > G; vector seen_v; vector ord; vector lowlink; int root = 0; void dfs(int v, int& first_ptr) { assert(0 <= v && v < N); seen_v[v] = true; //行きがけ順 ord[v] = lowlink[v] = first_ptr++; for (int i = 0; i < (int)G[v].size(); i++) { int next_v = G[v][i].to; if (!seen_v[next_v]) { //行先の頂点をまだ見ていない。 G[v][i].seen = true; dfs(next_v, first_ptr); lowlink[v] = min(lowlink[v], lowlink[next_v]); } else if(!G[next_v][G[v][i].rev].seen) {//逆に辿らない。 //行先の頂点を既に見ている、かつ逆辺を見ていない。v → next_v = G[v][i] は後退辺 (backward edge) lowlink[v] = min(lowlink[v], ord[next_v]); } } return; } public: Lowlink(int _N) : N(_N), G(_N), seen_v(_N, false), ord(_N, -1), lowlink(_N, -1) { }; //辺の追加 void add_edge(int from, int to) { assert(0 <= from && from < N); assert(0 <= to && to < N); G[from].push_back(edge{ to, (int)G[to].size(), false }); G[to].push_back(edge{ from, (int)G[from].size() - 1, false }); }; //初期化 void reset(){ G.assign(N, vector()); seen_v.assign(N, false); ord.assign(N, -1); lowlink.assign(N, -1); } //根の変更 void set_root(int v) { root = v; } void dfs() { int first_ptr = 0; dfs(root, first_ptr); return; } //そもそも連結であるか確認 bool is_connected() { for(int v = 0; v < N; v++) { if (!seen_v[v]) return false; } return true; } bool is_bridge(int from, int to) { //dfs実行後である確認。 assert(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; } bool is_articulation(int v) { //dfs実行後である確認。 assert(ord[0] != -1); assert(0 <= v && v < N); if (v == root) { int cnt = 0; rep(i, (int)G[v].size()) { if (G[v][i].seen) cnt++; } return (cnt != 1 && cnt != 0); //cnt != 1 だけだと、頂点が1つだけの連結グラフでバグる。(cnt == 0 で、頂点 0 は連結点でない) } else { rep(i, (int)G[v].size()) { int child = G[v][i].to; if (G[v][i].seen) { if (lowlink[child] >= ord[v]) return true; } } return false; } } }; signed main() { int N; cin >> N; vector a(N), b(N); rep(i, N) { cin >> a.at(i) >> b.at(i); a[i]--; b[i]--; } Lowlink G(N); rep(i, N) { G.add_edge(a[i], b[i]); //G.add_edge(b[i], a[i]); } G.dfs(); vector res; rep(i, N) { //if (!G.is_bridge(a[i], b[i]) && !G.is_bridge(b[i], a[i])) res.push_back(i + 1); if (!G.is_bridge(a[i], b[i])) res.push_back(i + 1); } cout << res.size() << endl; rep(i, (int)res.size()) { if (i != res.size() - 1) cout << res[i] << " "; else cout << res[i] << endl; } }