22982번 - 선인장의 독립집합 스페셜 저지

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

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

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

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

• $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$)
• 입력으로 주어지는 수는 모두 정수다.

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

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