P8173 [CEOI 2021] Newspapers

译自 CEOI2021 Day1 T3. [Newspapers](https://hsin.hr/ceoi/competition/ceoi2021_day1_tasks.pdf)。

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

输入第一行包含两个整数 $N$ 和 $M$，代表这张图的点数和边数。 接下来 $M$ 行两个整数 $u_i$，$v_i$，表示图上有一条连接 $u_i$，$v_i$ 的边。 输入保证图上无重边。

如果不存在成功的策略 $A$，仅输出一行一个字符串 `NO`。 否则，第一行应输出一个字符串 `YES`。 第二行应输出该策略最小的 $k$。 第三行应包含 $k$ 个整数，其中第 $i$ 个整数表示 $a_i$。

#### 样例解释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$ 轮，可以证明，任何一组最优策略都不会超出这个限制。 每个子任务的得分等于该子任务内得分最小的测试点得分。