#P4797. [CEOI2015 Day1] 波将金的路径

[CEOI2015 Day1] 波将金的路径

题目描述

译自 CEOI2015 Day1 T1「Potemkin cycle

简要题意 \, 给一张无向图,V=N,|V|=N, E=R|E|=R。请找一条简单路径,设该路径的点集为 VV',要求:V4|V'| \ge 4,且 VV' 的导出子图只含该路径本身(也就是一条链)。


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

  • m4m \geq 4

  • 经过的每个结点互不相同(即对于所有iji \neq j满足sisjs_i \neq s_j

  • 对于 i=1,,m1i = 1,\dots,m - 1,满足 sis_isi+1s_{i + 1} 直接连接,且 sms_ms1s_1 直接连接。

  • 序列中的结点没有其他的边(即对于所有 i<ji < j,使得 ji+1j \neq i + 1i1i \neq 1 或者是 jmj \neq m,结点 sis_isjs_j 之间没有边)。

输入格式

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

接下来 RR 行,其中第 ii 行包括两个不同的正整数 aia_ibi(1ai,biN)b_i(1 \leq a_i,b_i \leq N),表示结点 aia_ibib_i 之间有一条边。

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

输出格式

输出序列 s1,,sms_1,\dots,s_m,表示问题描述的序列(如果有多解任意输出一个)。如果无解,输出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

提示

NNRR 的上限如下表所示:

数据点 131-3 454-5 676-7 8108-10
NN 的上限 1010 100100 300300 1 0001\ 000
RR 的上限 4545 1 0001\ 000 20 00020\ 000 100 000100\ 000