Background

Translated from CEOI 2021 Day 1 T3. Newspapers.

Problem Description

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<k$), there must be an edge between $b_i$ and $b_{i+1}$. Note that $A$ has no such restriction.

We say Ankica’s strategy $A$ is successful if and only if for any valid $B$, there exists $i\in[1,k]$ such that $a_i=b_i$.

If such a strategy exists, output one with the minimum possible $k$.

Input Format

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.

Output Format

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$.

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

Hint

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:

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