Removing Vertices

Time limit2sMemory limit1024 MB

Summary

Given a graph where every cycle passes through vertex 0, remove the fewest vertices other than 0 so no cycles remain, and print which ones.

Level: Medium7 of 10
Topics: Dynamic programming, Tree, DFS, Graph
Solved: No attempts yet

Problem

You are given an undirected graph with $(n + 1)$ vertices numbered from $0$ to $n$ . The graph has no loops and no multiple edges. Every cycle passes through vertex $0$ . Remove the minimum possible number of vertices so that the graph has no cycles. Vertex $0$ cannot be removed.

Input

The first line contains 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 the next $m$ lines contains two integers $a$ and $b$ , the endpoints of an edge ( $0 \le a, b \le n$ ). It is guaranteed that every cycle passes through vertex $0$ .

Output

On the first line, print one integer $k$ , the minimum number of vertices to remove. On the second line, print the $k$ vertex numbers to remove in any order. If several optimal answers exist, print any one of them.

Examples2

Example 1
Input
```
4 6
0 1
1 2
2 0
0 3
3 4
4 0
```
Expected output
```
2
1 3
```
Example 2
Input
```
3 5
0 1
1 2
2 0
2 3
3 0
```
Expected output
```
1
2
```