멕시코 계곡

멕시코시티는 '멕시코 계곡'이라 불리는 아름다운 분지에 자리 잡고 있는데, 이곳은 오래전만 해도 대부분이 호수였다. 1300년경 아스텍의 종교 지도자들은 제국의 수도를 세우기 위해 호수 한가운데를 메우라고 명령했고, 오늘날 그 호수는 완전히 덮여 있다.

아스텍족이 오기 전, 호숫가에는 $c$개의 도시가 있었다. 이 도시들 중 일부는 서로 상업 협정을 맺고 있었다. 협정을 맺은 두 도시 사이에서는 배로 물자를 실어 날랐으며, 어떤 두 도시든 호수를 가로지르는 하나의 선분으로 이을 수 있었다.

훗날 왕들은 이 교역을 정리하여, 호숫가의 모든 도시를 잇는 하나의 교역로를 만들었다. 이 교역로는 다음 조건을 모두 만족해야 한다.

• 어느 도시에서 출발해도 되지만, 출발한 도시와 다른 도시에서 끝나야 한다.
• 모든 도시를 정확히 한 번씩 방문한다.
• 연이어 방문하는 두 도시는 반드시 상업 협정을 맺고 있어야 한다.
• 연이어 방문하는 두 도시는 호수를 가로지르는 선분으로 이어진다.
• 배들이 충돌하지 않도록, 교역로는 절대 자기 자신과 교차하지 않는다.

그림에서 (굵은 선과 가는 선을 포함한) 모든 선은 상업 협정을 나타내며, 굵은 선들은 도시 2에서 출발해 도시 5에서 끝나는 교역로를 이룬다. 이 교역로는 자기 자신과 교차하지 않는다. 예를 들어 $2 \to 6 \to 5 \to 1$ 같은 경로는 스스로 교차하므로 허용되지 않는다.

도시들은 호수를 따라 시계 방향으로 $1$번부터 $c$번까지 번호가 매겨져 있다.

$c$와 상업 협정 목록이 주어질 때, 위 조건을 모두 만족하는 교역로를 구성하는 프로그램을 작성하라.

• 첫째 줄: 정수 $c$.
• 둘째 줄: 상업 협정의 개수를 나타내는 정수 $n$.
• 다음 $n$개의 줄: 각 줄에는 하나의 상업 협정으로 이어진 두 도시가 공백으로 구분된 두 정수로 주어진다. 각 협정은 한 번씩만 주어지며 방향이 없다.

모든 조건을 만족하는 교역로는 여러 개일 수 있다(특히 어떤 교역로와 그 역순은 둘 다 유효하다). 그중 사전순으로 가장 앞서는 교역로 하나를 출력한다.

교역로는 방문하는 순서대로 나열한 도시 번호의 수열로 본다. 두 교역로를 앞에서부터 비교하여, 처음으로 달라지는 위치에서 더 작은 도시 번호를 갖는 쪽이 사전순으로 더 앞선다. 선택한 교역로를 $c$개의 줄에 출력하되, $i$번째 줄에는 $i$번째로 방문하는 도시를 적는다.

조건을 모두 만족하는 교역로가 존재하지 않으면 $-1$만 한 줄에 출력한다.

• $3 \le c \le 1000$ — 호숫가에 있는 도시의 수.