P8173 [CEOI 2021] Newspapers

Translated from CEOI 2021 Day 1 T3. [Newspapers](https://hsin.hr/ceoi/competition/ceoi2021_day1_tasks.pdf).

Ankica and Branko play a chasing game on an undirected connected graph. The game consists of several rounds, and each round has the following two steps: - **Ankica guesses which vertex Branko is currently at**. Specifically, she guesses that Branko is at some fixed vertex. If she is correct, Branko is caught and the game ends. Otherwise: - **Branko moves across one edge**. In other words, Branko moves to an adjacent vertex. Note that he **cannot** stay in place. Given the graph, determine whether Ankica can always catch Branko in a finite number of steps, no matter where Branko starts and how he moves. More formally, denote Ankica’s guessing strategy by $A=(a_1,a_2,\dots,a_k)$, where $a_i$ is the vertex she guesses in her $i$-th guess. Similarly, denote Branko’s movement by $B=(b_1,b_2,\dots,b_k)$, where $b_i$ is his position before round $i$. Moreover, for any two adjacent elements $b_i$ and $b_{i+1}$ in $B$ ($1\leq i

The first line contains two integers $N$ and $M$, representing the number of vertices and edges in the graph. The next $M$ lines each contain two integers $u_i$, $v_i$, indicating that there is an edge connecting $u_i$ and $v_i$. The input guarantees that the graph has no multiple edges and no self-loops.

If there is no successful strategy $A$, output a single line containing the string `NO`. Otherwise, the first line should output the string `YES`. The second line should output the minimum $k$ for such a strategy. The third line should contain $k$ integers, where the $i$-th integer is $a_i$.

#### Sample Explanation 1  If Branko initially is at vertex $1$, then he will be caught. Otherwise, he must move to vertex $1$, and then he will be caught. #### Sample Explanation 2  If Branko initially is on the cycle $(1,2,3)$ and is not equal to $a_1$, then according to the subsequent $a$, it is always possible to construct a $B$ that makes $A$ unsuccessful. #### Subtasks All testdata satisfy $1\leq N\leq 1000$, $N-1\leq M\leq \frac{N\times (N-1)}{2}$. The Constraints for each subtask are as follows: | Subtask ID | Points | Constraint | | :--------: | :----: | :----------------------------------------------------------: | | $1$ | $12$ | $1\leq N\leq 20$ | | $2$ | $8$ | $1\leq N\leq 1000$, $M=N-1$, and every vertex $u\in[1，N-1]$ has an edge to $u+1$ | | $3$ | $80$ | $1\leq N\leq 1000$ | #### Scoring If you can only answer the first line correctly, you will get $50\%$ of the points for that test. If for all tests where the answer is `YES`, you provide a correct strategy that is not necessarily minimal in $k$, you will get $75\%$ of the points for that test. Note that the strategy you provide cannot exceed $5N$ rounds. It can be proven that any optimal strategy will not exceed this limit. The score for each subtask equals the minimum score among the tests in that subtask. Translated by ChatGPT 5