시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5781409024.000%

문제

캠프의 마지막 날에 선물 교환 이벤트를 하려고 한다. 모든 학생들이 각자 두 개씩 선물을 준비해 와서 두 명의 친구에게 주는 것이다. 이벤트를 준비하던 중, 조교들은 이러한 이벤트가 불화를 일으킬 수 있음을 알게 되었다. 참석한 학생들 중 일부 학생들은 선물을 못 받거나 하나만 받게 되는 데 비해, 인기가 많은 학생들은 선물을 세 개 또는 그 이상 받게 되는 것이다.

그래서 조교들은 모든 학생들이 두 개의 선물을 주고, 또한 모든 학생들이 정확히 두 개의 선물만을 받도록 이벤트를 준비하고자 한다. 이를 위해 각각의 학생이 선물을 주고자 하는 두 명의 학생이 누구인지를 미리 알아내었다. 리스트를 살펴보던 조교들은, 몇 명의 학생을 추려 내면 모든 학생이 정확히 두 개의 선물을 받을 수 있다는 것을 알게 되었다.

참여한 모든 학생이 정확히 선물을 두 개씩 받도록 이벤트에 참여할 학생들을 결정하는 프로그램을 작성하시오. 단, 이벤트에 참여하는 학생의 수가 최대가 되도록 해야 한다.

입력

첫째 줄에 학생의 수 N(3 ≤ N ≤ 200,000)이 주어진다. 학생은 1부터 N까지 번호가 매겨진다. 이어서 다음 N개 줄에는 각 학생이 선물을 주고자 하는 두 학생의 번호가 빈 칸을 사이에 두고 주어진다. 자기 자신에게 선물을 주는 경우는 없으며, 두 사람의 번호는 항상 다르다.

출력

첫째 줄에 최대로 참여시킬 수 있는 학생의 수를 출력한다. 둘째 줄에는 참여할 학생들의 번호를 증가하는 순서대로 빈 칸을 사이에 두고 출력한다. 가능한 방법이 둘 이상인 경우 그 중 한 가지만 출력한다. 만일 한 명의 학생도 참여시킬 수 없는 경우 첫째 줄에 0만을 출력한다.

예제 입력 1

5
2 3
3 5
1 5
3 5
1 2

예제 출력 1

4
1 2 3 5

출처

  • 문제를 번역한 사람: author5