在魔法之国比托兰迪（Bitolandia），几个世纪以来一直居住着 $n$ 位贤者，并存在着 $m$ 条咒语。根据古老的魔法定律，每条咒语恰好被 $n - 2$ 位贤者所知。所有的贤者都知道每条咒语恰好被这么多贤者所知，但他们不知道总共存在多少条咒语。对于每一条他所知的咒语，每位贤者都确切地知道还有哪些其他贤者也知道这条咒语。然而，他并不知道还有多少条他所不知道的咒语存在。特别地，可能存在某位贤者一条咒语都不知道的情况——在这种情况下，他不知道是否有任何咒语存在（但他仍然知道，如果存在任何咒语，那么一定会有 $n - 2$ 位贤者知道它）。

贤者们每天中午都会在百兆字节森林（Stumegabajtowy lesie）聚会，但他们完全不交谈，只是互相问候并进行冥想，晚上则各自回到自己的小屋。除了在聚会时看到彼此，贤者们没有任何其他交流方式。他们这样做是因为担心那条约束他们的古老传统：如果一位贤者得知存在一条他不知道的咒语，那么他必须在最近的午夜悄悄离开，去流亡，且永远不再回到比托兰迪。

有一天，一位旅行者来到了比托兰迪。经过几天的观察，他决定参加贤者们的聚会，并在会上鲁莽地向所有人宣布：“我注意到，你们中至少有一个人知道至少一条咒语！”

旅行者还将在比托兰迪停留接下来的 $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$ 个整数，表示缺席聚会的贤者编号，按升序排列。

样例

样例输入 1

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 1
2
2 3
1 2 3
-1
2 4
1 2 4 5

说明 1

在第一个测试用例中，第二位贤者不知道任何咒语，因此他会在第一天晚上离开，不会出现在第一次聚会上。在第二个测试用例中，每位贤者都知道一条只有他自己不知道的咒语。当所有贤者在第一次聚会上见面时，每个人都会想：“如果其他人不知道任何咒语，他们昨晚就会离开；既然他们都在这里，那么他们一定知道一些我不知道的咒语！”，因此每个人都会在第二天晚上离开，不会出现在第二次聚会上。在第三个测试用例中，贤者们本不会参加第二次聚会，但旅行者会提前离开比托兰迪，因此不会等到任何缺席情况发生。