문제를 푸는 문제 (잘못 구현한 오일러 회로)

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

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

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

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

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 \le N, M \le 200{,}000$)

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

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

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