드라이브 투어

N(3 <= N <= 256)개의 도시가 있는 나라가 있다. 몇몇 도시 쌍은 도로로 연결되어 있다. 도시는 1번부터 N번까지 번호가 붙어 있고, 처음에는 1번 도시에 있다.

드라이브는 1번 도시에서 N번 도시까지 간 뒤 다시 1번 도시로 돌아오는 경로이다. 1번에서 N번으로 갈 때는 방문하는 도시 번호가 매번 증가해야 하고, N번에서 1번으로 돌아올 때는 방문하는 도시 번호가 매번 감소해야 한다. 1번 도시와 N번 도시는 두 방향 모두에서 사용할 수 있지만, 그 밖의 도시는 갈 때와 돌아올 때에 중복해서 방문할 수 없다.

도로 정보가 주어졌을 때, 서로 다른 도시를 최대한 많이 방문하는 드라이브 경로를 구하라.

첫째 줄에 도시의 수 N이 주어진다.

이후 여러 줄에 도로 정보를 나타내는 두 자연수 P, Q가 주어진다. 이는 P번 도시와 Q번 도시 사이에 도로가 있음을 뜻한다. 도로는 양방향으로 존재하지만, 실제 드라이브 경로는 위의 도시 번호 증가/감소 조건을 따라야 한다.

P = Q = 0이 주어지면 입력이 끝난다.

조건을 만족하는 드라이브 경로가 없으면 첫째 줄에 0을 출력한다.

가능한 경로가 있으면 첫째 줄에 방문한 서로 다른 도시의 최대 개수를 출력한다. 둘째 줄에는 1번 도시에서 시작해 N번 도시에 도착한 뒤 다시 1번 도시로 돌아오는 경로를 도시 번호 순서대로 출력한다. 최적 경로가 여러 개라면 그중 아무 것이나 출력해도 된다.