#P4797. [Ceoi2015]Potemkin cycle

    ID: 3914 传统题 1000ms 888MiB 尝试: 9 已通过: 3 难度: 8 上传者: 标签>CF2500提高+/省选-弦图最大势搜索完美消除序列无向连通分量广度优先搜索路径恢复

[Ceoi2015]Potemkin cycle

题目描述

简要题意

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


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

  • m≥4m \geq 4

  • 经过的每个结点互不相同(即对于所有 i≠ji \neq j 满足 si≠sjs_i \neq s_j)

  • 对于 i=1,…,m−1i = 1,\dots,m - 1,满足 sis_i 与 si+1s_{i + 1} 直接连接,且 sms_m 与 s1s_1 直接连接。

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

输入格式

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

接下来 RR 行,其中第 ii 行包括两个不同的正整数 aia_i 和 bi(1≤ai,bi≤N)b_i(1 \leq a_i,b_i \leq N),表示结点 aia_i 与 bib_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