Problem Description

Translated from CEOI2015 Day1 T1 “Potemkin cycle”.

Brief statement Given an undirected graph with $|V|=N$ and $|E|=R$. Find a simple cycle. Let the vertex set of this cycle be $V'$. It must satisfy: $|V'| \ge 4$, and the subgraph induced by $V'$ contains only this cycle itself.

Duke Potemkin’s territory can be viewed as an undirected graph. He asks you to find a route whose visited vertices are represented by a sequence $s_1,\dots,s_m$, and it must satisfy the following:

• $m \geq 4$.

• All visited vertices are pairwise distinct (i.e., for all $i \neq j$, $s_i \neq s_j$).

• For $i = 1,\dots,m - 1$, $s_i$ is directly connected to $s_{i + 1}$, and $s_m$ is directly connected to $s_1$.

• There are no other edges among the vertices in the sequence (i.e., for all $i < j$ such that $j \neq i + 1$ and either $i \neq 1$ or $j \neq m$, there is no edge between $s_i$ and $s_j$).

Input Format

The first line contains two non-negative integers $N$ and $R$ $(0 \leq N \leq 1\ 000, 0 \leq R \leq 100\ 000)$, representing the number of vertices and the number of roads (edges), respectively.

The next $R$ lines each contain two distinct positive integers $a_i$ and $b_i$ $(1 \leq a_i,b_i \leq N)$, indicating that there is an edge between vertices $a_i$ and $b_i$.

It is guaranteed that there is at most one edge between any pair of vertices.

Output Format

Output the sequence $s_1,\dots,s_m$ that satisfies the requirements in the description (if there are multiple solutions, output any one). If there is no solution, output no.

5 6
1 2
1 3
2 3
4 3
5 2
4 5

2 3 4 5

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

no

Hint

The upper limits of $N$ and $R$ are shown in the table below:

Translated by ChatGPT 5