#P15843. [2024国家队集训杭州站]图

[2024国家队集训杭州站]图

图(graph)

题目描述

给出一个 nn 个点、RR 条边的无向图,结点从 11 开始标号。

请你求出一个结点序列 SS,满足以下条件:

  1. 序列长度 m>3m>3
  2. 序列中的结点互不相同;
  3. 序列中相邻结点之间有边,且 S1S_1SmS_m 之间也有边;
  4. 序列中的点构成的导出子图只有 mm 条边。

换句话说,你需要找出一个长度大于 33诱导环。如果不存在这样的序列,请输出 no

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 nnRR,分别表示结点数和边数。

接下来的 RR 行,每行包含两个正整数 xxyy,保证 1x,yn1\le x,y\le n,表示 xxyy 之间存在一条无向边。

输出格式

输出到标准输出。

输出任意一个满足题目描述中条件的序列。如果不存在,请输出 no

样例 1 输入

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

样例 1 输出

2 3 4 5

样例 2 输入

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

样例 2 输出

no

数据范围

测试点 NN\le RR\le
131\sim 3 1010 4545
454\sim 5 100100 10001000
676\sim 7 300300 2000020000
8108\sim 10 10001000 100000100000