P4797 [CEOI 2015] Potemkin Cycle (Day1)

**Translated from [CEOI2015](https://ceoi2015.fi.muni.cz/tasks.php) Day1 T1 “[Potemkin cycle](https://ceoi2015.fi.muni.cz/day1/eng/day1task1-eng.pdf)”.** **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$).

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 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`.

The upper limits of $N$ and $R$ are shown in the table below: |Test case group|$1-3$|$4-5$|$6-7$|$8-10$| |-|:-:|:-:|:-:|:-:| |Upper limit of $N$|$10$|$100$|$300$|$1\ 000$| |Upper limit of $R$|$45$|$1\ 000$|$20\ 000$|$100\ 000$| Translated by ChatGPT 5