신문

크로아티아 아이들 사이에서 인기 있는 놀이 노래 "Ulovi me, ulovi me, kupit ću ti novine!"는 나를 잡으면 신문을 사 줄게라는 뜻이다.

안키차와 브랑코는 방향이 없고 연결된 그래프에서 술래잡기를 한다. 브랑코는 그래프 위를 돌아다니고, 안키차는 그를 잡으려 한다. 게임은 턴 단위로 진행되며, 한 턴은 다음 두 단계로 이루어진다.

• 안키차가 브랑코의 위치를 추측한다. 그녀는 특정 노드 하나를 골라 브랑코가 지금 거기에 있다고 추측한다. 추측이 맞으면 브랑코는 잡히고 게임이 끝난다. 틀리면,
• 브랑코가 현재 위치에 연결된 간선 하나를 따라 이동한다. 그는 이웃한 노드 중 하나로 옮겨 간다. 브랑코는 제자리에 머무를 수 없다.

그래프가 주어졌을 때, 브랑코가 어떻게 움직이든, 어디서 출발하든 항상 그를 잡는 유한한 전략이 안키차에게 있는지 판단하라.

형식적으로 안키차의 전략은 배열 $A = (a_1, a_2, \dots, a_k)$로 나타낸다. 여기서 $a_i$는 i번째 턴에서 그녀가 하는 추측이며, 브랑코가 노드 $a_i$에 있다고 추측한다는 뜻이다. 브랑코의 이동은 배열 $B = (b_1, b_2, \dots, b_k)$로 나타낸다. 여기서 $b_i$는 i번째 턴 직전에 브랑코가 있는 노드이다. 연속한 두 원소 $b_i$와 $b_{i+1}$ ($1 \le i < k$) 사이에는 두 노드를 잇는 간선이 그래프에 있어야 한다. 배열 $A$에는 이런 제약이 없다.

안키차의 전략이 성공적이라는 것은, 즉 최대 $k$ 턴 안에 브랑코를 잡는다는 것은, 길이가 $k$인 유효한 배열 $B$마다 $a_i = b_i$를 만족하는 $i$ ($1 \le i \le k$)가 존재한다는 뜻이다.

그런 전략이 존재하면 $k$를 최소로 하는 전략을 찾아라.

성공하지만 최적은 아닌 전략(즉 $k$가 최소가 아닌 전략)을 제시하면 부분 점수를 받을 수 있다. 자세한 내용은 채점 절을 참고하라.

첫 번째 줄에 그래프의 노드 수 $N$과 간선 수 $M$이 주어진다 ($N - 1 \le M \le \frac{N(N-1)}{2}$). 노드는 1부터 $N$까지 번호가 매겨져 있다.

이어지는 $M$개의 줄 중 $i$번째 줄에는 공백으로 구분된 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$)가 주어지며, 이는 노드 $u_i$와 $v_i$를 잇는 무방향 간선이 있다는 뜻이다. 같은 간선이 두 번 나오지 않으며, 그래프는 연결되어 있다.

안키차에게 성공적인 전략이 없으면 첫 번째 줄에 "NO"를 출력하고 종료한다.

그렇지 않으면 첫 번째 줄에 "YES"를 출력한다. 두 번째 줄에는 수 $k$를, 세 번째 줄에는 $k$개의 수 $a_1, a_2, \dots, a_k$를 출력한다.