[AdditionalFile2786.zip](file://AdditionalFile2786.zip?type=additional_file)

#2786. 「CEOI2015 Day1」波将金的路径

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 CEOI2015 Day1 T1「Potemkin cycle」

简要题意 $\,$ 给一张无向图，$|V|=N,$ $|E|=R$。请找一个简单环，设该环的点集为 $V'$，要求：$|V'| \ge 4$，且 $V'$ 的导出子图只含该路径本身。

波将金公爵的领土可以视作一张无向图，他要求你找到一条路线，经过的结点以序列 $s_1,\dots,s_m$ 表示，且满足以下要求：

• $m \geq 4$

• 经过的每个结点互不相同（即对于所有 $i \neq j$ 满足 $s_i \neq s_j$）

• 对于 $i = 1,\dots,m - 1$，满足 $s_i$ 与 $s_{i + 1}$ 直接连接，且 $s_m$ 与 $s_1$ 直接连接。

• 序列中的结点没有其他的边（即对于所有 $i < j$，使得 $j \neq i + 1$ 且 $i \neq 1$ 或者是 $j \neq m$，结点 $s_i$ 和 $s_j$ 之间没有边）。

输入格式

第一行，两个非负整数 $N$ 和 $R(0 \leq N \leq 1\ 000,0 \leq R \leq 100\ 000)$，分别表示结点的个数和道路的个数。

接下来 $R$ 行，其中第 $i$ 行包括两个不同的正整数 $a_i$ 和 $b_i(1 \leq a_i,b_i \leq N)$，表示结点 $a_i$ 与 $b_i$ 之间有一条边。

保证每两个结点最多有一条边连接。

输出格式

输出序列 $s_1,\dots,s_m$，表示问题描述的序列（如果有多解任意输出一个）。如果无解，输出 no。

样例 1

输入

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

输出

2 3 4 5

样例 2

输入

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

输出

no

数据范围与提示

$N$ 与 $R$ 的上限如下表所示：