정점 제거

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

요약

모든 사이클이 정점 0을 지나는 그래프에서 0번을 제외한 정점을 최소한으로 지워 사이클이 없게 만들고, 지울 정점 번호를 출력합니다.

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

문제

정점이 $0$ 부터 $n$ 까지 번호로 매겨진 $(n + 1)$ 개인 양방향 그래프가 주어진다. 이 그래프에는 자기 루프와 중복 간선이 없다. 모든 사이클은 정점 $0$ 을 지난다. 그래프에 사이클이 없도록 정점을 최소한으로 제거한다. 정점 $0$ 은 제거할 수 없다.

입력

첫 줄에 정점 $0$ 을 제외한 정점의 수 $n$ 과 간선의 수 $m$ 이 주어진다 ( $1 \le n \le 10^5$ , $1 \le m \le 10^6$ ). 다음 $m$ 개의 줄에는 각각 간선으로 연결된 두 정점 $a$ 와 $b$ 가 주어진다 ( $0 \le a, b \le n$ ). 모든 사이클이 정점 $0$ 을 지난다는 조건은 입력에서 보장된다.

출력

첫 줄에 제거해야 하는 정점의 최소 개수 $k$ 를 출력한다. 둘째 줄에는 제거할 정점의 번호 $k$ 개를 순서에 상관없이 출력한다. 최적해가 여러 개라면 그중 아무것이나 출력한다.

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