#line 1 "main.cpp" #include #include #include #include #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 2 "/home/user/Library/graph/functional_graph.hpp" #include #include #include #line 6 "/home/user/Library/graph/functional_graph.hpp" /** * @brief Namori cycle / なもり閉路 * @param g a simple connected undirected graph with |E| = |V| */ std::deque get_namori_cycle(const std::vector >& g) { int n = g.size(); { // check the namori-ty int m = 0; REP (i, n) { m += g[i].size(); } assert (m == 2 * n); } std::deque stk; std::vector used(n); auto go = [&](auto&& go, int i, int parent) -> int { if (used[i]) return i; stk.push_back(i); used[i] = true; for (int j : g[i]) if (j != parent) { int k = go(go, j, i); if (k != -1) return k; } assert (stk.back() == i); stk.pop_back(); used[i] = false; return -1; }; int i = go(go, 0, -1); assert (i != -1); // fails if the graph is not simple while (stk.front() != i) { stk.pop_front(); } return stk; } #line 7 "main.cpp" using namespace std; std::vector solve(int n, const std::vector >& edges) { std::vector > g(n); std::map, int> lookup; REP (i, edges.size()) { auto [a, b] = edges[i]; g[a].push_back(b); g[b].push_back(a); lookup[std::make_pair(a, b)] = i; lookup[std::make_pair(b, a)] = i; } auto cycle = get_namori_cycle(g); std::vector ans; REP (i, cycle.size()) { int a = cycle[i]; int b = cycle[(i + 1) % cycle.size()]; ans.push_back(lookup[std::make_pair(a, b)]); } return ans; } int main() { int n; scanf("%d", &n); std::vector > edges(n); REP (i, n) { int a, b; scanf("%d%d", &a, &b); -- a; -- b; edges[i] = std::make_pair(a, b); } std::vector ans = solve(n, edges); printf("%d\n", (int)ans.size()); REP (i, ans.size()) { printf("%d%c", ans[i] + 1, i + 1 < ans.size() ? ' ' : '\n'); } return 0; }