시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 114 17 15 27.273%

문제

N(3≤N≤256)개의 도시로 이루어진 나라가 있다. 이들 중 몇 개의 도시들은 서로 도로로 연결되어 있다. 당신은 당신의 취미 생활인 자동차 드라이브를 즐기려고 한다. 각각의 도시는 1, 2, 3, …, N의 번호가 붙어 있고, 현재 당신은 1번 도시에 위치하고 있다. 당신은 N번 도시까지 갔다가 다시 돌아오고자 한다.

1번 도시에서 N번 도시로 갈 때에는 도시의 번호가 증가하는 순서로 가려고 하며, N번 도시에서 1번 도시로 돌아올 때에는 도시의 번호가 감소하는 순서로 가려고 한다. 또한, 갈 때 방문했던 도시를 올 때에 다시 방문할 수는 없다.

도로에 대한 정보가 주어졌을 때, 최대한 많은 도시를 방문하는 드라이브 경로를 찾으라.

입력

첫째 줄에 N이 주어진다. 다음 줄부터는 도로에 대한 정보를 나타내는 두 자연수 P, Q가 주어진다. 이는 P번 도시와 Q번 도시 사이에 도로가 있음을 의미한다. P=Q=0이 입력으로 주어지면 입력의 끝을 나타낸다.

출력

첫째 줄에 방문한 도시의 개수를 출력한다. 다음 줄에는 드라이브 경로를 출력한다. 1번 도시에서 N번에 갔다가 다시 돌아올 수 없는 경우에는 0을 출력한다.

예제 입력

5
1 2
1 3
1 5
2 3
2 4
3 5
4 5
0 0

예제 출력

5
1 3 5 4 2 1

힌트

출처

  • 빠진 조건을 찾은 사람: august14