Edge = Struct.new(:to, :id) N = gets.to_i G = Array.new(N + 1){ [] } (1 .. N).each do |i| a,b = gets.split.map(&:to_i) G[a] << Edge.new(b, i) G[b] << Edge.new(a, i) end active = Array.new(N + 1) parent = Array.new(N + 1) depth = Array.new(N + 1) active[N] = G[N].size parent[N] = N depth[N] = 0 u = N loop do j = (active[u] -= 1) e = G[u][j] v = e.to if j < 0 u = parent[u] elsif !active[v] active[v] = G[v].size depth[v] = depth[u] + 1 parent[v] = u u = v elsif v != parent[u] cycle = [e.id] w = v until w == u cycle << G[w][active[w]].id w = G[w][active[w]].to end puts cycle.size puts cycle.join(" ") break end end