//無向グラフでの各種dfs //計算量 パス検出:O(E+V)、閉路検出:O(E+V) //verified with //https://yukicoder.me/problems/no/1254 #include using namespace std; struct io_setup{ io_setup(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; struct Graph{ vector> es; vector used; vector keep; const int n; Graph(int n) : n(n){ es.resize(n), used.resize(n); } void add_edge(int from, int to, bool directed = false){ es[from].emplace_back(to); if(!directed) es[to].emplace_back(from); } bool trace(int now, int t){ used[now] = true; if(now == t) {keep.emplace_back(now); return true;} for(auto &e : es[now]){ if(used[e]) continue; if(trace(e, t)) {keep.emplace_back(now); return true;} } return false; } vector find_path(int s, int t){ keep.clear(), fill(begin(used), end(used), 0); trace(s, t), reverse(begin(keep), end(keep)); return keep; } int detect(int now, int pre){ if(used[now]++) return 1; for(auto &e: es[now]){ if(e == pre) continue; int k = detect(e, now); if(k == 2) return 2; if(k == 1) {keep.emplace_back(now); return used[now];} } return 0; } vector find_loop(){ keep.clear(), fill(begin(used), end(used), 0); for(int i = 0; i < n; i++){ if(used[i]) continue; detect(i, -1); if(!keep.empty()) {reverse(begin(keep), end(keep)); return keep;} } return keep; } }; int main(){ int V; cin >> V; Graph G(V); map, int> mp; for(int i = 0; i < V; i++){ int u, v; cin >> u >> v; u--, v--; G.add_edge(u, v); mp[minmax(u, v)] = i; } vector loop = G.find_loop(); int n = loop.size(); cout << n << '\n'; for(int i = 0; i < n; i++){ int j = (i+1)%n; cout << mp[minmax(loop[i], loop[j])]+1 << ' '; } cout << '\n'; }