포템킨 순환로

포템킨 공작은 시찰단에게 보여 주려고 급히 지은 가짜 마을로 이름이 높다. 공작은 영지 안의 닫힌 경로를 따라 시찰단을 안내하고, 경로가 지나는 마을 터마다 배우 무리가 이동식 마을을 세워 주민 행세를 한다. 시찰단이 자리를 뜨면 배우들은 마을을 해체해 시찰단보다 먼저 다음 터로 달려간다.

경로를 고르는 데는 셈이 필요하다. 시찰단은 예정된 경로를 잠시 벗어나 주변을 둘러보기도 하는데, 이미 지나온 터로 되돌아가면 마을이 서 있던 자리가 텅 비어 있어 속임수가 들통난다. 또 제대로 인상을 남기려면 경로가 적어도 네 곳의 터를 지나야 한다.

영지의 지도, 곧 터 사이를 잇는 양방향 직통 도로 목록이 주어진다. 도로가 엇갈리는 곳은 정교한 고가 구조로 처리해서, 시찰단은 도로의 양 끝 터가 아닌 곳에서 다른 도로로 갈아탈 수 없다.

다음 조건을 모두 만족하는 터의 수열 $s_1, \dots, s_m$을 찾아라.

• $m \ge 4$이다.
• 모든 터가 서로 다르다. 즉 $i \ne j$이면 $s_i \ne s_j$이다.
• $i = 1, \dots, m - 1$에 대해 $s_i$와 $s_{i+1}$을 잇는 직통 도로가 있고, $s_m$과 $s_1$을 잇는 직통 도로도 있다.
• 수열에 속한 터 사이에 그 밖의 직통 도로는 없다. 즉 $j \ne i + 1$이고 $(i, j) \ne (1, m)$인 모든 $i < j$에 대해 $s_i$와 $s_j$를 잇는 직통 도로가 없다.

첫째 줄에 터의 수 $N$과 직통 도로의 수 $R$이 주어진다 ($0 \le N \le 1000$, $0 \le R \le 100\,000$). 터의 번호는 1번부터 $N$번까지다. 이어지는 $R$개의 줄에는 서로 다른 두 정수 $a_i$와 $b_i$가 주어지며 ($1 \le a_i, b_i \le N$), 터 $a_i$와 터 $b_i$를 잇는 직통 도로가 있다는 뜻이다. 두 터를 잇는 도로는 많아야 하나다.

조건을 만족하는 수열이 없으면 no를 출력한다.

조건을 만족하는 수열은 보통 여럿이므로, 아래 규칙이 고르는 하나만 한 줄에 출력한다. 터 번호는 공백 하나로 구분한다.

터 $v$에 대해, 지도에서 $v$와 $v$에 도로로 이어진 터를 모두 지우고 남은 것을 $G_v$라 하자. 두 터 $a$와 $b$가 각각 $v$와 도로로 이어져 있고, $a$와 $b$를 잇는 도로는 없으며, $a$에서 $b$로 가는 경로 중 내부 터가 모두 $G_v$에 속하는 것이 있으면 $a$와 $b$를 $v$의 우회 쌍이라 하자.

1. 우회 쌍이 있는 가장 작은 터를 $v$로 잡는다. 그런 터가 없으면 no를 출력한다.
2. $v$의 우회 쌍을 $a < b$인 $(a, b)$로 적고, $a$가 가장 작은 쌍을, 그중에서 $b$가 가장 작은 쌍을 고른다.
3. $a$, $b$와 $G_v$의 터만 남기고 그 사이의 도로를 모두 살린 지도를 $H$라 하자. $H$에서 $a$부터 $b$까지 가는 최단 경로 중 사전순으로 가장 앞서는 것을 고른다. 곧 $a$에서 출발해 매번 $b$까지 남은 거리가 가장 짧게 유지되는 터 가운데 번호가 가장 작은 터로 이동한다.
4. $v$, $a$, 그 경로의 내부 터를 차례대로, 마지막으로 $b$를 출력한다.

이렇게 만든 수열은 언제나 네 조건을 만족하고, 규칙이 남기는 답은 하나뿐이다.