题目描述
译自 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$,满足 $si$ 与 $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
input
5 6
1 2
1 3
2 3
4 3
5 2
4 5
output
2 3 4 5
样例 2
input
4 5
1 2
2 3
3 4
4 1
1 3
output
no
数据范围与提示
$N$ 与 $R$ 的上限如下表所示:
数据点 | $1-3$ | $4-5$ | $6-7$ | $8-10$ |
---|---|---|---|---|
$N$ 的上限 | $10$ | $100$ | $300$ | $1\ 000$ |
$R$ 的上限 | $45$ | $1\ 000$ | $20\ 000$ | $100\ 000$ |