시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 0 0 0 0.000%

문제

이 문제에는 제출할 수 없다. "문제를 푸는 문제" 문제를 참조하라.


간선에 방향이 없는 그래프가 주어졌을 때, 한 정점에서 시작하여 모든 간선을 정확히 한 번씩 지나서 다시 그 정점으로 돌아오는 경로를 오일러 회로라고 한다.

연결된 그래프에서 오일러 회로가 존재할 필요충분조건은 모든 정점의 차수가 짝수인 것이다. 따라서 단순 그래프 순회만으로 그래프에 오일러 회로가 존재하는지 알아낼 수 있다. 하지만 오일러 회로 하나를 실제로 만들어내는 것은 다른 문제이다. 오일러 회로가 존재하는 연결된 그래프가 주어질 때, 오일러 회로를 찾는 문제를 생각해 보자.

구대기는 "이렇게 하면 오일러 회로가 만들어지지 않을까?"라는 간단한 생각에 다음 알고리즘을 고안했다.

  1. 한 정점 v를 고른다.
  2. 다음을 계속 반복한다.
    1. 현재 보고 있는 정점에 인접한 간선 중, 사용하지 않은 것을 하나 고른다. 그런 간선이 없으면 멈춘다.
    2. 그 간선을 사용하면서 반대쪽 정점으로 이동한다.

과연 이 알고리즘으로 오일러 회로를 만들 수 있을까? 그렇지 않다. 우선 이 알고리즘이 정점 v에서 멈춘다는 사실은 증명할 수 있다. 2-1 단계에서 현재 보고 있는 정점이 v가 아니면, 사용하지 않은 간선은 항상 홀수 개이므로 0개보다 크기 때문이다. 하지만 v에서 멈춘다고 해서 모든 간선을 사용하는 것은 아니다.

위 그래프를 보자. 만약 v를 1번 정점으로 잡는다면 1, 4, 2, 6, 1 순서로 정점을 방문하여 오일러 회로를 구성하는 데 실패할 수도 있다. 한편, v를 2번 정점으로 잡는다면 2-1단계에서 어떤 간선을 사용하더라도 오일러 회로가 반드시 만들어진다.

오일러 회로를 구성하는 데 실패할 수 있는 정점을 모두 찾아 구대기의 코를 납작하게 해주자.

입력

첫째 줄에 그래프의 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N, M ≤ 200,000)

다음 M개의 줄에는 간선의 양 끝점의 번호가 주어진다. 번호는 1 이상 N 이하이다.

주어지는 그래프는 단순 그래프이다. 즉 같은 정점을 연결하는 간선은 없으며, 같은 정점 쌍을 연결하는 두 간선도 없다. 또한 그래프는 연결되어 있고, 오일러 회로가 존재함이 보장된다.

출력

첫째 줄에는 오일러 회로를 구성하는 데 실패할 수 있는 정점의 개수를 출력한다. 다음 줄에는 그러한 정점의 번호를 오름차순으로 모두 출력한다.

서브태스크 1 (172645134점)

N = M

서브태스크 2 (488967702점)

N, M ≤ 10

서브태스크 3 (652141864점)

N, M ≤ 2,000

서브태스크 4 (833728947점)

추가 제약 조건이 없다.

예제 입력 1

7 8
1 4
1 6
4 2
6 2
2 5
2 7
5 3
7 3

예제 출력 1

6
1 3 4 5 6 7

출처

Contest > 구데기컵 > 진짜 최종 구데기컵 2 🎁번

채점

  • 예제는 채점하지 않는다.