지구를 구하자!

슈퍼히어로 부대가 타노스와의 전투에서 지구를 지키는 사람들을 돕기 위해 달려가고 있습니다. 슈퍼히어로들은 지금 타이탄에 있고, 우주 셔틀은 한 대뿐입니다. 이 셔틀에는 승객 $k$명과 조종사 한 명이 탈 수 있습니다. 부대는 현명한 지도자 한 명과 슈퍼히어로 $n$명으로 구성됩니다. 일부 슈퍼히어로 쌍은 서로 싫어하고, 말다툼을 하거나 심지어 서로를 해칠 수도 있습니다. 하지만 지도자가 곁에 있으면 슈퍼히어로들은 절대 충돌하지 않습니다. 지도자가 이를 엄격히 막기 때문입니다.

셔틀은 지도자가 직접 조종합니다. 지도자는 모든 슈퍼히어로를 지구로 옮길 수 있는지 알고 싶어 합니다. 이동 과정은 다음과 같습니다.

• 지도자와 함께 슈퍼히어로 최대 $k$명이 셔틀에 탑니다. 타이탄에 남은 슈퍼히어로 중에는 충돌하는 쌍이 있으면 안 됩니다. 그렇지 않으면 끔찍한 결과가 생길 수 있습니다.
• 셔틀이 지구로 날아갑니다. 비행 중에는 셔틀에 탄 슈퍼히어로들이 지도자 곁에 있으므로 싸우지 않습니다.
• 지구에서 셔틀에 타고 있던 슈퍼히어로 전원이 내립니다. 이때 지구에 있는 슈퍼히어로 중에 충돌하는 쌍이 있을 수 있습니다. 지도자가 곁에 있으므로 싸우지 않습니다.
• 슈퍼히어로 최대 $k$명이 셔틀에 탑니다. 지구에 남은 슈퍼히어로 중에는 충돌하는 쌍이 없어야 합니다.
• 셔틀이 타이탄으로 날아갑니다.
• 타이탄에서 셔틀에 타고 있던 슈퍼히어로 전원이 내립니다. 이때 타이탄에 있는 슈퍼히어로 중에 충돌하는 쌍이 있을 수 있습니다.

위 과정은 모든 슈퍼히어로와 지도자가 지구에 도착할 때까지 순환하며 반복됩니다. 필요하다면 지도자는 슈퍼히어로 없이 빈 셔틀을 몰고 행성 사이를 오갈 수 있습니다. 지도자가 없는 행성에는 충돌하는 쌍이 있으면 안 됩니다. 그 밖의 충돌 쌍에 대한 제약은 없습니다.

충돌하는 쌍의 목록이 주어집니다. 지도자가 모든 슈퍼히어로를 지구로 옮기는 순서를 찾도록 도와주세요. 옮길 수 없다면 그렇다고 알려주세요. 비행 횟수를 최소화할 필요는 없습니다. 다만 지도자는 비행 횟수가 최대 $100\,000$회인 방법을 원합니다. 주어진 제약에서는, 모든 슈퍼히어로를 지구로 옮길 방법이 존재하면 비행 $100\,000$회 이하의 방법도 반드시 존재함을 증명할 수 있습니다.

첫 줄에 정수 $n$, $m$, $k$가 주어집니다. 각각 슈퍼히어로의 수, 충돌하는 쌍의 수, 셔틀에 탈 수 있는 슈퍼히어로의 수입니다 ($1 \le n \le 15$, $0 \le m \le n \cdot (n - 1) / 2$, $1 \le k \le 15$).

이어지는 $m$개의 줄에는 충돌하는 슈퍼히어로의 번호 $a_i$, $b_i$ 쌍이 주어집니다 ($1 \le a_i, b_i \le n$, $a_i \neq b_i$).

각 쌍은 최대 한 번만 나타납니다. 입력에 $a_i$, $b_i$ 쌍이 있다면 $b_i$, $a_i$ 쌍은 입력에 없습니다.

모든 슈퍼히어로와 지도자를 지구로 옮길 수 없으면 $-1$을 한 줄에 출력합니다.

그렇지 않으면 첫 줄에 셔틀이 수행하는 비행 횟수 $t$를 출력합니다. 이 횟수가 끝나면 모든 슈퍼히어로와 지도자가 지구에 있어야 합니다 ($t \le 100\,000$). 이어지는 $t$개의 줄 중 $i$번째 줄에는 $i$번째 비행에서 셔틀에 탄 슈퍼히어로의 목록을 출력합니다. 줄의 앞에는 목록의 크기 $q_i$를 쓰고, 이어서 셔틀에 탄 서로 다른 슈퍼히어로 번호 $q_i$개를 씁니다.