루미 알고리즘

#1535플래티넘Monopoly

PO 2022 결선코딩출제 Joakim Blikstad영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Jocke and his friends usually play Monopoly with each other. After countless games, they have grown tired of the usual rules, so they have changed them a bit.

First, they choose a suitably sized country. They then look at the road network in the country and choose a sequence of different cities v_1, v_2, …, v_k that form a cycle. This means that there is a direct road between cities v_i and v_{i+1} for all 1 ≤ i < k and between v_k and v_1, just like on a Monopoly board. Then they travel to the country and play by driving around the cycle in their cars to buy and sell properties with real money.

However, there is a restriction that makes it difficult to carry out the game: they must find a suitable cycle in the road network. Some countries have very large road networks. What makes it even more difficult is that the cycle must have an even number of roads, otherwise, the rules won't work (“Free Parking” does not end up in the middle, which creates an unbalanced game).

Given all the cities in the country and the roads between pairs of cities, find a cycle consisting of an even number of roads if there is one.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Illustration of the countries in the three example cases.

Input

The first line contains two integers N (1 ≤ N ≤ 10^5) and M (0 ≤ M ≤ min(2 · 10^5, (N(N-1))/2), the number of cities and the number of roads in the road network, respectively.

Then follow M lines, each with two integers a and b, which means that there is a road between cities a and b in the country (1 ≤ a ≠ b ≤ N). It is guaranteed that there are no multiple roads between the same pair of cities in the country.

Output

If there is no even cycle, print a single line with the string “NO”.

If there is an even cycle, print a single line with the string “YES”. Then, you should print such a cycle. First, print a line with an even integer k (4 ≤ k ≤ N), the number of cities in your cycle. On the next line, print k different integers v_1, v_2, …, v_k (1 ≤ v_i ≤ N) separated by spaces: the cities in your cycle. It must hold that there are roads between the cities (v_1, v_2), (v_2, v_3), …, (v_{k-1}, v_k), (v_k, v_1).

If there are multiple possible cycles, you can print any of them.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
118N ≤ 10
216N ≤ 100 and M ≤ 200
317The cities can be divided into two parts so that no road goes between two cities in the same part.
413All cities in the country have a direct road to at most 2 cities.
520All cities in the country have a direct road to at most 3 cities.
616No additional constraints.

예제

예제 1

입력
4 5
1 2
1 3
2 3
3 4
4 1
출력
YES
4
3 2 1 4 

예제 2

입력
5 6
1 2
1 3
1 4
1 5
2 3
4 5
출력
NO

예제 3

입력
7 6
1 7
3 4
4 5
5 6
6 3
5 2
출력
YES
4
6 3 4 5 

출처 표기

출처: Programmeringsolympiaden 2022년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.