Removing Vertices

시간 제한2초메모리 제한1024 MB

요약

모든 사이클이 정점 0을 지나는 그래프에서 0을 제외한 정점을 최소 개수만큼 지워 비순환 그래프로 만든다.

난이도: 보통10점 중 7점
유형: 그래프, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

You are given an bidirectional graph with $(n + 1)$ vertices numbered from $0$ to $n$ . There are no loops and no multiple edges in this graph. Additionally, all cycles pass through vertex 0. Your task is to remove the minimum possible number of vertices so that there are no cycles in the graph. You can not remove the vertex number 0.

입력

On the first line, there are two integers $n$ and $m$ : the number of vertices excluding vertex $0$ and the number of edges ( $1 \le n \le 10^5$ , $1 \le m \le 10^6$ ).

Each of next $m$ lines contains two integers $a$ and $b$ : the numbers of vertices connected by an edge ( $0 \le a, b \le n$ ).

It is guaranteered that all cycles pass through vertex $0$ .

출력

On the first line, print one integer $k$ : the minimum possible number of vertices to remove. On the second line, print $k$ integers: the numbers of the vertices to remove in any order. If there are several optimal answers, print any one of them.

예제2

예제 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
```