선인장의 독립집합

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

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

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