페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6249
스페셜 저지
서브태스크

노드 제거하기 1s 1024MB

문제

그래프 G는 0번부터 N번까지 총 N+1개의 노드로 이루어진 그래프로 아래와 같은 성질이 있다.

  • 루프(연결하는 두 노드가 같은 간선)가 존재하지 않는다.

  • 중복되는 간선이 존재하지 않는다.

  • 모든 사이클은 0번 노드를 지난다.

노드를 최소 개수만큼 제거하여 모든 사이클을 제거하시오. ( 0번 노드는 제거할 수 없다! )

*그래프 G 의 모든 간선은 양방향이며, 사이클은 같은 간선을 두 번 이상 사용하지 않고 처음 노드로 돌아오는 간선의 집합을 의미한다.


입력

첫 줄에 정수 N과 간선의 수 M이 주어진다. (1 \le N \le 10^5, 1 \le M \le 10^6)

이어 M줄에 걸쳐 각 간선이 연결하는 두 노드 a와 b가 주어진다. (0 \le a, b \le N, a \neq b).


출력

첫 번째 줄에 제거할 노드의 수를 출력한다.

두 번째 줄에 제거할 노드의 번호를 공백으로 나누어 출력한다.

(가능한 답이 여러 가지라면 그 중 아무거나 출력한다.)


부분문제

번호 점수 조건
#15점

예제와 동일한 데이터만 주어짐

#225점

N \le 20

#370점

추가 제한 없음


예제 #1

4 6
0 1
1 2
2 0
0 3
3 4
4 0
2
1 3

예제 #2

3 5
0 1
1 2
2 0
2 3
3 0
1
2


출처

Open Cup 2014/2015 Stage 1: Grand Prix of SPb H번

로그인해야 코드를 작성할 수 있어요.