题目描述

题目译自 CEOI 2021 Day1 T3「Newspapers」

Ulovi me, ulovi me, kupit ću ti novine!

这是一首克罗地亚孩子们在做游戏时常唱的儿歌。翻译过来大概意思是：「抓住我，抓住我，我会给你买报纸！」。

Ankica 和 Branko 正在一张无向连通图上玩追逐游戏。Branko 正在图上移动，而 Ankica 试图去抓到他。这个游戏轮流进行，一轮由如下步骤组成：

• Ankica 猜 Branko 现在在哪儿。更确切地说，她会猜测 Branko 目前在某个特定的点处。如果她猜对了，Branko 就被抓住了，并且游戏结束，否则，
• Branko 通过一条恰与该点相连的边。换句话说，Branko 移向一个与他当前所在的点相邻的点。注意 Branko 不能停留在他当前所在的位置。

给定一张图，请确定 Ankica 是否有一个确定的策略可以在不论 Branko 如何进行游戏和任意起点位置的情况下永远可以抓到他。

形式化地说，我们用一个数组 $A=(a_1,a_2,\ldots,a_k)$ 代表 Ankica 的策略，这里 $a_i$ 表示 Ankica 在第 $i$ 轮猜的位置（即，她会猜 Branko 在点 $a_i$ 处）。

类似地，我们用一个数组 $B=(b_1,b_2,\ldots,b_k)$ 代表 Branko 的移动，这里 $b_i$ 表示 Branko 在第 $i$ 轮前所处的位置。此外，对于每两个连续的元素 $b_i$ 和 $b_{i+1}\ (1\le i<k)$，图上必须存在一条边连接 $b_i$ 和 $b_{i+1}$。注意对于数组 $A$ 没有这个要求。

如果对于任意合法且长度为 $k$ 的数组 $B$，都存在一个 $i\ (1\le i\le k)$ 满足 $a_i=b_i$，我们就称 Ankica 的策略是可以获胜的，即她会在最多 $k$ 轮抓到 Branko。

如果这样的策略存在，你需要找到一个 $k$ 最小的策略。

如果你可以找出一个可以获胜但不是最优的策略（即，一个 $k$ 不是最小的策略），你也可以获得一些分数。参考「数据范围及限制」部分了解更多细节。

输入格式

第一行两个整数 $N$ 和 $M\ (N-1\le M\le \frac{N(N-1)}{2}$，分别表示图上的点数和边数。图中的点从 $1$ 到 $N$ 编号。

接下来 $M$ 行，每行两个整数 $u_i,v_i\ (1\le u_i,v_i\le N,u_i\neq v_i)$，用一个空格隔开，表示连接 $u_i$ 和 $v_i$ 的一条无向边。

输入中没有任何边会出现超过一次，并且图保证连通。

输出格式

如果对于 Ankica 没有可以获胜策略，只需要输出一行 NO 后退出程序即可。

否则，第一行输出 YES。

第二行输出一个整数 $k$，意义如题目描述。

第三行包含 $k$ 个整数 $a_1,a_2,\ldots,a_k$，意义如题目描述。

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

YES
2
1 1

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

NO

数据范围与提示

子任务编号	附加条件	分值
$1$	$1\le N\le 20$	$12$
$2$	$1\le N\le 10^3,M=N-1$，每个节点 $u=1,\ldots,N-1$ 和 $u+1$ 相连	$8$
$3$	$1\le N\le 10^3$	$80$

如果你的程序第一行中正确地输出了 YES，但没能输出一种获胜策略，那么你将获得测试点 $50\%$ 的分数。

如果你的程序第一行中正确地输出了 YES，并且给出了一个不是最优的获胜策略，那么你将获得测试点 $75\%$ 的分数。此外，为了获得这部分分数，输出的策略中游戏进行轮数 $k$ 必须至多为 $5N$。可以证明最优策略中游戏轮数不超过 $5N$。

对于每个子任务，得分为子任务中测试点的最少得分。