题目描述

题目译自 PA 2022 Runda 3 Mędrcy

几个世纪以来，神奇的 Bitoland 一直是 $n$ 个贤者和 $m$ 条咒语的家园。根据古老的魔法法则，每条咒语恰好被 $n-2$ 个贤者知道。所有的贤者都知道每条咒语都被他们中的一些确定的人所知，但他们不知道到底有多少条咒语存在。每个贤者，对于他所知道的每一条咒语，都清楚地知道其他哪些贤者知道它。然而，贤者不知道存在多少他不知道的咒语。特别的，一个贤者可能不知道任何咒语——在这种情况下，他不知道是否存在咒语（但他仍然知道，如果存在咒语，则正好有 $n-2$ 个贤者会知道它们）。

贤者每天中午都会在 Stumegabyte 森林里聚会，但他们在那里不会互相交流，他们只是各自问候对方并进行冥想，晚上他们都回到自己的小屋。贤者除了在见面时看到对方之外，并没有其他任何方式的交流。他们这样做是因为他们害怕约束他们的古老传统，其中规定，如果一个贤者发现有他不知道的咒语，他必须在当天午夜神不知鬼不觉地离开这里，并且永远不能回到 Bitoland。

有一天，一个流浪者来到了 Bitoland。在观察了几天这些贤者之后，他决定去见他们，在那里他不明智地对所有贤者宣布：「我已经注意到，你们中至少有一个贤者知道至少一条咒语！」

流浪者将在 Bitoland 再停留 $k$ 天（最多一个月），每天观察聚会情况，但不会再多说什么。在这段时间里，会不会有一天，一些贤者不会在聚会上出现？

我们假设贤者的推断是完美的，也就是说，如果他们中的任何一个人能够从流浪者宣布的内容和他们所掌握的关于咒语的信息中推断出什么，那么现实情况一定是这样的，并且他们会这么做。

输入格式

第一行一个正整数 $t$，表示测试点个数。

对于每个测试点，第一行包含三个整数 $n,m,k\ (3\le n,1\le m,1\le k\le 30)$，分别表示贤者人数，咒语个数和流浪者会观察会议的天数。贤者从 $1$ 到 $n$ 编号。

接下来 $m$ 行，每行两个整数 $a_i,b_i\ (1\le a_i<b_i\le n)$，表示除了贤者 $a_i$ 和 $b_i$ 之外其他所有贤者都知道这条咒语。

保证一组数据中所有测试点的 $n$ 之和不超过 $1\ 000$，所有 $m$ 之和不超过 $3\ 000$。

输出格式

对于每组数据，如果接下来 $k$ 天的每一天，所有贤者都会来参加聚会，则输出一行 $-1$。否则输出两行。第一行包含两个整数 $d$ 和 $c$，其中 $d$ 表示有贤者没来聚会的最早的一次，$c$ 表示这一次没来聚会的贤者个数。第二行包含 $c$ 个整数，表示没来聚会的贤者编号，按从小到大的顺序输出。

4
3 2 7
1 2
2 3
3 3 7
1 2
2 3
1 3
5 3 1
1 5
2 4
1 5
5 2 2
2 4
1 5

1 1
2
2 3
1 2 3
-1
2 4
1 2 4 5