#include #include #include #include #include #include #include #include #include using namespace std; using ll = int64_t; #define rep(i, j, n) for (int i = j; i < (n); ++i) #define rrep(i, j, n) for (int i = (n)-1; j <= i; --i) template std::ostream& operator<<(std::ostream& os, std::vector& a) { os << "{"; for (size_t i = 0; i < a.size(); ++i) os << (i > 0 ? "," : "") << a[i]; return os << "}"; } [[maybe_unused]] constexpr ll MOD = 1000000007; [[maybe_unused]] constexpr int INF = 0x3f3f3f3f; [[maybe_unused]] constexpr ll INFL = 0x3f3f3f3f3f3f3f3fLL; struct Edge { int from, to; Edge(int f, int t) : from(f), to(t) {} }; using Edges = vector; using Graph = vector; class LowLink { public: LowLink(int n) : mGraph(n), mOrd(n), mLow(n), mUsed(n, false) {} void add_edge(int u, int v) { mGraph[u].emplace_back(u, v); mGraph[v].emplace_back(v, u); } // e(u,v)が橋 <=> ord[u] < low[v] // 頂点vが関節点 <=> ord[u] <= low[v]となるvの子uが存在 int dfs(int v, int pv, int k) { mUsed[v] = true; mOrd[v] = mLow[v] = k++; // 訪れた順 bool is_articulation = false; int cnt = 0; for (Edge nv : mGraph[v]) { if (!mUsed[nv.to]) { // まだ訪れてない ++cnt; k = dfs(nv.to, v, k); mLow[v] = min(mLow[v], mLow[nv.to]); is_articulation |= ~pv && mOrd[v] <= mLow[nv.to]; if (mOrd[v] < mLow[nv.to]) mBridges.emplace_back(minmax(v, nv.to)); } else if (nv.to != pv) { // 後退辺だったら mLow[v] = min(mLow[v], mOrd[nv.to]); } } is_articulation |= pv == -1 && cnt > 1; if (is_articulation) mArticulationPoints.push_back(v); return k; } void Init() { int k = 0; for (int i = 0; i < mGraph.size(); ++i) { if (!mUsed[i]) k = dfs(i, -1, k); } } vector> GetBridges() { return mBridges; } vector GetArticulationPoints() { return mArticulationPoints; } private: Graph mGraph; vector mOrd; vector mLow; vector mUsed; vector> mBridges; vector mArticulationPoints; }; int main() { int n, s, t; cin >> n; LowLink lowlink(n); vector> es; for (int i = 0; i < n; ++i) { cin >> s >> t; --s; --t; es.emplace_back(s, t); lowlink.add_edge(s, t); } lowlink.Init(); auto ans = lowlink.GetBridges(); map, bool> mp; for (auto p : ans) { mp[p] = true; mp[{p.second, p.first}] = true; } cout << n - ans.size() << '\n'; for (int i = 0; i < n; ++i) if (!mp[es[i]]) cout << i + 1 << " \n"[i == n - 1]; return 0; }