题目背景

译自 CEOI2021 Day1 T3. Newspapers。

题目描述

Ankica 和 Branko 在一张无向连通图上玩追逐游戏，游戏分为若干个回合，每一回合有如下两步：

• Ankica 猜测 Branko 现在在哪个结点。具体地，她将猜测 Branko 在某个特定的结点，如果正确，Branko 被抓住，游戏将会结束，否则：
• Branko 穿过一条边。换句话说，Branko将移动到一个相邻的结点，注意他不能不移动。

给出这张图，请求出 Ankica 是否总能在有限步内抓到 Branko 且不论 Branko 初始位置在哪以及如何移动。

更形式化地，我们把 Ankica 猜测的策略用 $A=(a_1,a_2,\dots,a_k)$ 表示，其中 $a_i$ 代表她第 $i$ 次猜测 Branko 在 $a_i$ 结点。

相似地，我们把 Branko 的移动也用 $B=(b_1,b_2,\dots,b_k)$ 表示，其中 $b_i$ 代表他在第 $i$ 回合前的位置。此外，对于 $B$ 中任意两个相邻的元素 $b_i$ 和 $b_{i+1}$（$1\leq i<k$），$b_i$ 和 $b_{i+1}$ 之间必定有一条边。注意对于 $A$ 没有这样的限制。

我们认为 Ankica 的猜测策略 $A$ 是成功的，当且仅当对于任意合法的 $B$ ，都存在 $i\in[1,k]$ 使得 $a_i=b_i$。

如果存在这样的策略，请输出使得 $k$ 最小的一组策略。

输入格式

输入第一行包含两个整数 $N$ 和 $M$，代表这张图的点数和边数。

接下来 $M$ 行两个整数 $u_i$，$v_i$，表示图上有一条连接 $u_i$，$v_i$ 的边。

输入保证图上无重边。

输出格式

如果不存在成功的策略 $A$，仅输出一行一个字符串 NO。

否则，第一行应输出一个字符串 YES。

第二行应输出该策略最小的 $k$。

第三行应包含 $k$ 个整数，其中第 $i$ 个整数表示 $a_i$。

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

如果 Branko 初始位于 $1$ 号结点，则他会被抓住，否则他必定会移动到 $1$ 号结点，然后被抓住。

样例解释2

若 Branko 初始在环 $(1,2,3)$ 上且不与 $a_1$ 相同，则根据之后的 $a$ 必定能构造出使 $A$ 不合法的 $B$。

子任务

所有测试点均满足 $1\leq N\leq 1000$，$N-1\leq M\leq \frac{N\times (N-1)}{2}$。

各子任务的约束条件如下：

子任务编号	分值	限制
$1$	$12$	$1\leq N\leq 20$
$2$	$8$	$1\leq N\leq 1000$，$M=N-1$，且每个结点 $u\in[1，N-1]$ 都与 $u+1$ 有边
$3$	$80$	$1\leq N\leq 1000$

评分细则

如果你仅能正确回答第一行，则你将得到该测试点 $50\%$ 的分数。

如果对于所有回答 YES 的测试点，你能提供一组 $k$ 非最小但正确的策略，你将得到该测试点 $75\%$ 的分数。注意，你提供的策略不能超过 $5N$ 轮，可以证明，任何一组最优策略都不会超出这个限制。

每个子任务的得分等于该子任务内得分最小的测试点得分。