모노폴리

Jocke와 그의 친구들은 보통 서로 모노폴리를 한다. 셀 수 없이 많은 게임을 한 뒤, 평소 규칙에 싫증이 난 그들은 규칙을 조금 바꾸었다.

먼저, 적당한 크기의 나라를 고른다. 그런 다음 그 나라의 도로망을 살펴보고, 사이클을 이루는 서로 다른 도시들의 수열 $v_1, v_2, \dots, v_k$을 고른다. 이는 모든 $1 \le i < k$에 대해 도시 $v_i$와 $v_{i+1}$ 사이에 직접 연결된 도로가 있고, $v_k$와 $v_1$ 사이에도 직접 연결된 도로가 있다는 뜻이며, 모노폴리 보드와 같다. 그런 다음 그 나라로 가서, 자동차로 사이클을 따라 돌면서 실제 돈으로 부동산을 사고파는 방식으로 게임을 한다.

하지만 게임을 실행하기 어렵게 만드는 제약이 있다. 도로망에서 적합한 사이클을 찾아야 한다. 일부 나라는 도로망이 매우 크다. 더욱 어렵게 만드는 점은 사이클의 도로 수가 짝수여야 한다는 것이다. 그렇지 않으면 규칙이 작동하지 않는다(``Free Parking''이 가운데에 놓이지 않아 불균형한 게임이 된다).

나라의 모든 도시와 도시 쌍 사이의 도로가 주어질 때, 짝수 개의 도로로 이루어진 사이클이 존재한다면 하나를 찾아라.

[!h]

세 예제 경우에 등장하는 나라의 그림.

채점

여러 테스트 그룹으로 구성된 테스트 세트로 풀이를 평가하며, 각 그룹에는 일정한 점수가 배정된다. 각 테스트 그룹에는 테스트 케이스 세트가 들어 있다. 테스트 그룹의 점수를 얻으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제약 조건

$1$ | 18 | $N \le 10$

$2$ | 16 | $N \le 100$ 및 $M \le 200$

$3$ | 17 | 도시들을 두 부분으로 나누어, 같은 부분에 속한 두 도시 사이에는 도로가 없도록 할 수 있다.

$4$ | 13 | 나라의 모든 도시는 최대 2개의 도시와 직접 연결된 도로를 갖는다.

$5$ | 20 | 나라의 모든 도시는 최대 3개의 도시와 직접 연결된 도로를 갖는다.

$6$ | 16 | 추가 제약 조건이 없다.

첫째 줄에 도로망의 도시 수와 도로 수를 각각 나타내는 두 정수 $N$ ($1 \le N \le 10^5$)와 $M$ ($0 \le M \le \min(2 \cdot 10^5, \frac{N(N-1)}{2}$)가 주어진다.

이어서 $M$개의 줄이 주어지며, 각 줄에는 두 정수 $a$와 $b$가 주어진다. 이는 나라에서 도시 $a$와 $b$ 사이에 도로가 있다는 뜻이다($1 \le a \neq b \le N$). 나라에서 같은 도시 쌍 사이에 여러 도로가 존재하지 않음이 보장된다.

짝수 길이의 사이클이 없다면, 문자열 ```NO`''만 포함하는 한 줄을 출력한다.

짝수 길이의 사이클이 있다면, 문자열 ```YES`''만 포함하는 한 줄을 출력한다. 그런 다음, 그러한 사이클을 출력해야 한다. 먼저 사이클에 포함된 도시 수를 나타내는 짝수 정수 $k$ ($4 \le k \le N$)를 한 줄에 출력한다. 다음 줄에는 사이클에 포함된 도시를 나타내는 $k$개의 서로 다른 정수 $v_{1}, v_{2}, \ldots, v_{k}$ ($1 \le v_{i} \le N$)를 공백으로 구분하여 출력한다. 도시 $(v_{1}, v_{2}), (v_{2}, v_{3}), \ldots, (v_{k-1}, v_{k}), (v_{k}, v_{1})$ 사이에 도로가 존재해야 한다.

가능한 사이클이 여러 개라면 그중 아무거나 출력할 수 있다.