벌통

왼쪽은 예제 $1$, 오른쪽은 예제 $2$.

양봉가 Bie는 자신의 벌들이 숲으로 이사하면 잘 지낼 것이라는 결론을 내렸다. 그래서 Ljungström 씨에게 그의 숲에 벌통을 놓아도 된다는 허락을 받았다. Ljungström의 숲은 정점 $N$개와 간선 $M$개로 이루어진 무방향 그래프로 나타낼 수 있다. 정점에는 $1$부터 $N$까지 번호가 매겨져 있다. 먼저 Bie는 자신의 벌통을 놓을 정점을 $1$개에서 $N-K$개 사이로 고를 수 있다. 하지만 Ljungström 역시 양봉가이므로, Bie가 벌통을 놓고 나면 Ljungström도 자신의 벌통을 놓을 것이다! Bie는 Ljungström이 자신이 고르지 않은 정점 중 번호가 가장 큰 정점 $K$개를 항상 고른다는 것을 알고 있다. Ljungström의 벌들은 유난히 공격적이므로, Bie는 자신의 정점 중 어느 것도 이 정점들 중 어느 것과도 인접하지 않도록(간선을 공유하지 않도록) 하는 것이 중요하다.

당신의 과제는 Ljungström이 남은 정점 중 인덱스가 가장 큰 정점 $K$개를 골라도 그중 어느 것도 당신이 고른 정점 중 어느 것과도 인접하지 않도록, 최대 $N-K$개의 정점으로 이루어진 집합을 찾는 것이다.

점수

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$12$| $K=1$

$2$ |$15$| $N \leq 15$

$3$ |$25$| $N \leq 2000$, $M \leq 4000$

$4$ |$13$| $K \leq 15$

$5$ |$35$| 추가 제한 없음.

첫째 줄에는 세 정수 $N$ ($2 \le N \le 2 \cdot 10^5$), $M$ ($1 \leq M \leq 4\cdot 10^5$), 그리고 $K$ ($1 \leq K \leq N-1$)가 주어진다.

이어지는 $M$개의 줄에는 각각 두 정수 $u_i$와 $v_i$ ($1 \leq u_i, v_i \leq N$)가 주어지며, 이는 $i$번째 간선이 정점 $u_i$와 $v_i$를 연결한다는 뜻이다.

그래프에는 한 정점에서 자기 자신으로 이어지는 간선이나 같은 정점 쌍 사이를 잇는 여러 간선이 없다. 또한 그래프는 연결되어 있음이 보장된다. 즉, 간선을 따라 이동하여 모든 정점 쌍 사이를 오갈 수 있다.

유효한 정점 집합이 없다면 ``-1''를 출력한다.

그렇지 않다면 먼저 집합에 포함된 정점의 수인 정수 $L$을 한 줄에 출력한다. 그다음 줄에는 당신이 고른 정점의 인덱스인 정수 $a_1, a_2, \dots , a_L$를 $L$개 출력한다.

해가 여러 개라면 그중 아무거나 출력해도 된다.