시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)76141221.053%

문제

무방향 그래프 $G\left(V, E\right)$에서 정점의 부분집합 $S$에 속한 모든 정점 쌍이 서로 인접하지 않으면 $S$를 독립 집합(independent set)이라고 한다. 임의의 그래프에 대한 최대 독립 집합 문제는 NP-Complete 문제로 다항시간에 해결할 수 있는지 없는지 아직 밝혀지지 않았다.

선인장 그래프(cactus graph)는 모든 간선이 최대 한 개의 사이클에 속한 연결된 무방향 그래프다. 즉, 임의의 서로 다른 두 사이클이 최대 하나의 공통 정점을 가지는 무방향 연결 그래프를 의미한다.

선인장 그래프에서의 최대 독립 집합을 구해보자.

입력

다음과 같이 입력이 주어진다.

$N\ M$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$
  • $N$은 정점의 개수이고 $M$은 간선의 개수이다. ($1 \le N \le 100\,000$, $N - 1 \le M \le 150\,000$)
  • $u_i$ $v_i$는 정점 $u_i$와 $v_i$를 잇는 간선이 존재한다는 뜻이다. ($1 \le u, v \le N$, $u \ne v$)
  • 입력으로 주어지는 수는 모두 정수다.

출력

첫 번째 줄에 주어진 선인장 그래프에 대한 최대 독립 집합의 크기를 출력한다.

두 번째 줄에 최대 독립 집합에 속한 정점 번호를 크기 순으로 출력한다. 만약 가능한 최대 독립 집합이 여러 가지인 경우에는 아무거나 출력하면 된다.

예제 입력 1

10 12
1 2
1 5
1 8
2 3
3 4
4 1
5 6
6 7
7 1
8 9
9 10
10 1

예제 출력 1

6
2 4 5 7 8 10

예제 입력 2

9 10
1 2
2 3
3 4
4 5
5 1
1 6
6 7
7 8
8 9
9 1

예제 출력 2

4
2 4 6 8

예제 입력 3

15 17
1 2
2 3
3 1
3 4
4 5
5 6
6 7
6 8
8 9
9 3
2 10
10 11
11 12
12 13
12 14
14 15
15 2

예제 출력 3

7
3 5 7 8 11 13 15