ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
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번

ログインしないとコードを書けません。