타워 디펜스 게임

바이티는 타워 디펜스라는 컴퓨터 게임을 하고 있다. 목표는 감시탑을 세워서 자기 영토 전체를 지키는 것이다. 영토에는 도시가 여러 개 있고, 일부 도시 쌍은 양방향 도로로 이어져 있다. 어떤 도시에 감시탑을 세우면 그 탑은 자기 도시와 도로로 직접 이어진 모든 도시를 지킨다.

바이티가 감시탑을 어디에 세울지 고민하고 있을 때 누나 바이테아가 방에 들어왔다. 화면에 뜬 지도를 잠깐 보더니 이렇게 말했다. "뭘 그렇게 고민해? 딱 봐도 탑 $k$개면 충분한데."

재미를 망친 누나를 방에서 내보낸 바이티는 다음 수를 생각하기 시작했다. 자존심 때문에 탑을 $k$개보다 많이 세울 수는 없다. 대신 비장의 수가 하나 남아 있다. 개량형 감시탑 기술을 연구하면 된다. 개량형 감시탑은 세워진 도시와 바로 옆 도시뿐 아니라 더 멀리 있는 도시까지 지킨다. 정확히 말하면, 도시 $u$에 세운 개량형 감시탑은 다음 중 하나를 만족하는 도시 $v$를 지킨다.

• $u = v$이다.
• $u$와 $v$를 직접 잇는 도로가 있다.
• $u$와 도로로 이어져 있으면서 $v$와도 도로로 이어진 도시 $w$가 있다.

바이티는 여전히 탑을 $k$개 이하로만 세우려 하지만, 그 탑을 전부 개량형으로 만드는 것은 개의치 않는다.

첫째 줄에 세 정수 $n$, $m$, $k$가 공백 하나로 구분되어 주어진다 ($2 \le n \le 500\,000$, $0 \le m \le 1\,000\,000$, $1 \le k \le n$). 각각 도시의 수, 도로의 수, 바이테아가 말한 수 $k$이다.

도시에는 $1$번부터 $n$번까지 번호가 붙어 있다. 다음 $m$개 줄에는 도로 정보가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $a_i$와 $b_i$가 주어지며 ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), $a_i$번 도시와 $b_i$번 도시가 양방향 도로로 직접 이어져 있다는 뜻이다. 두 도시를 잇는 도로는 많아야 하나이다.

조건을 만족하는 배치는 여러 가지이므로, 바이티는 그중 하나를 규칙으로 미리 정해 두었다. 번호가 작은 도시부터 차례로 살펴보다가 지금까지 세운 탑이 하나도 지키지 못하는 도시를 만나면 그 도시에 개량형 감시탑을 세운다. 이미 지켜지고 있는 도시에는 아무것도 세우지 않는다.

두 줄을 출력한다. 첫째 줄에는 이 규칙으로 세운 탑의 개수 $r$을 출력한다. 둘째 줄에는 탑을 세운 도시 $r$개의 번호를 증가하는 순서로 공백 하나씩 두고 출력한다.

바이테아의 말이 맞다고, 즉 일반 감시탑 $k$개로 영토 전체를 지킬 수 있다고 가정해도 좋다. 그러면 위 규칙이 세우는 탑은 절대 $k$개를 넘지 않으므로 항상 $1 \le r \le k$이다.