현자들

마법의 나라 비톨란디아에는 예로부터 $n$명의 현자가 살고 있고, $m$개의 주문이 있습니다. 고대 마법의 법칙에 따라 각 주문은 정확히 $n-2$명의 현자가 알고 있습니다. 현자들은 모두 이 사실을 알지만, 주문이 모두 몇 개인지는 아무도 모릅니다. 각 현자는 자신이 아는 주문마다 어떤 다른 현자들이 그 주문을 아는지 정확히 압니다. 하지만 자신이 모르는 주문이 몇 개인지는 알지 못합니다. 주문을 하나도 모르는 현자는 주문이 존재하는지조차 알지 못합니다. 다만 주문이 존재한다면 정확히 $n-2$명의 현자가 알고 있을 것이라는 점은 압니다.

현자들은 매일 정오에 스투메가바이트 숲에서 만납니다. 그곳에서는 대화를 나누지 않습니다. 서로 인사를 나눈 뒤 명상하고, 밤이 되면 각자 오두막으로 돌아갑니다. 이 만남에서 서로를 보는 것 외에는 어떤 방식으로도 소통하지 않습니다. 이렇게 조심하는 이유는 오래된 전통 때문입니다. 현자가 자신이 모르는 주문이 존재한다는 사실을 알게 되면, 그다음 날 밤 자정까지 아무도 모르게 비톨란디아를 떠나야 하며, 다시는 돌아올 수 없습니다.

어느 날 한 여행자가 비톨란디아에 도착했습니다. 며칠 동안 현자들을 지켜본 그는 어느 만남에 찾아가 모두에게 이렇게 말했습니다. "여러분 중 적어도 한 명은 적어도 하나의 주문을 알고 있다는 것을 알았습니다!"

여행자는 앞으로 $k$일(최대 한 달) 동안 비톨란디아에 머물며 매일의 만남을 지켜보겠지만, 더는 아무 말도 하지 않습니다. 그동안 현자 중 일부가 만남에 나오지 않는 날이 올까요?

현자들은 완벽하게 추론한다고 가정합니다. 여행자의 말과 자신이 가진 주문에 관한 정보로 무언가를 추론할 수 있다면, 반드시 그렇게 합니다.

첫 줄에 테스트 케이스의 수 $t$가 주어집니다. 이어서 각 테스트 케이스가 주어집니다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $k$ ($3 \le n$; $1 \le m$; $1 \le k \le 30$)가 주어집니다. 각각 현자의 수, 주문의 수, 여행자가 더 머무는 날의 수입니다.

이어지는 $m$개의 줄에는 두 정수 $a_i$, $b_i$ ($1 \le a_i < b_i \le n$)가 주어집니다. 이는 번호 $a_i$번과 $b_i$번 현자를 제외한 모든 현자가 아는 주문이 있다는 뜻입니다. 현자들은 1번부터 $n$번까지 번호가 매겨져 있습니다.

한 파일에서 $n$의 합은 1000을 넘지 않고, $m$의 합은 3000을 넘지 않는다고 보장합니다.

여행자가 지켜보는 $k$번의 만남에 모든 현자가 빠짐없이 참석하면 $-1$을 한 줄에 출력합니다.

그렇지 않으면 두 줄을 출력합니다. 첫 줄에는 두 정수 $d$와 $c$를 출력합니다. $d$는 현자 중 일부가 만남에 나오지 않는 가장 이른 날의 번호이고, $c$는 그날 나오지 않는 현자의 수입니다. 둘째 줄에는 그날 나오지 않는 현자의 번호를 오름차순으로 $c$개 출력합니다.

첫 번째 테스트 케이스에서 2번 현자는 주문을 하나도 알지 못합니다. 그래서 첫날 밤에 떠나고 첫 만남에 나오지 않습니다. 두 번째 테스트 케이스에서는 각 현자가 자기만 아는 주문을 하나씩 압니다. 첫 만남에서 모두 모이면 각 현자는 이렇게 생각합니다. "다른 현자들이 주문을 하나도 모른다면 전날 밤에 떠났을 것이다. 여기 있다는 것은 내가 모르는 주문을 그들이 안다는 뜻이다!" 그래서 모두 둘째 날 밤에 떠나고 둘째 만남에 나오지 않습니다. 세 번째 테스트 케이스에서는 현자들이 둘째 만남에 나오지 못하지만, 여행자가 그 전에 비톨란디아를 떠나기 때문에 결석은 한 번도 관찰되지 않습니다.