Problem Description

Warning: abusing this problem to attack the judge will result in your account being banned.

This problem is translated from PA 2022 Round 3 Mędrcy.

For centuries, the magical Bitoland has been home to $n$ sages and $m$ spells. According to ancient magical laws, each spell is known by exactly $n-2$ sages. All sages know that each spell is known by some specific people among them, but they do not know how many spells exist in total. For each spell a sage knows, they know exactly which other sages know it. However, a sage does not know how many spells exist that they do not know. In particular, a sage may know no spells at all. In that case, they do not know whether any spells exist (but they still know that if spells exist, then exactly $n-2$ sages know each of them).

Every day at noon, the sages gather in the Stumegabyte Forest. They do not communicate there; they only greet each other and meditate, and in the evening they all return to their huts. Apart from seeing each other when they meet, the sages have no other way to communicate. They do this because they fear an old tradition that binds them. It states that if a sage discovers that there exists a spell they do not know, they must secretly leave at midnight of that day and can never return to Bitoland.

One day, a wanderer arrived in Bitoland. After observing the sages for a few days, he decided to meet them. There, unwisely, he announced to all sages: “I have noticed that at least one sage among you knows at least one spell!”

The wanderer will stay in Bitoland for another $k$ days (at most one month), observing the gatherings each day, but he will not say anything else. During this time, will there be a day when some sages do not show up at the gathering?

We assume the sages’ reasoning is perfect. That is, if any of them can deduce something from the wanderer’s announcement and the information they have about spells, then it must be true in reality, and they will deduce it.

Input Format

The first line contains a positive integer $t$, the number of test cases.

For each test case, the first line contains three integers $n, m, k$, denoting the number of sages, the number of spells, and the number of days the wanderer will observe the meetings. The sages are numbered from $1$ to $n$.

The next $m$ lines each contain two integers $a_i, b_i$, meaning that all sages except sages $a_i$ and $b_i$ know this spell.

Output Format

For each test case, if on every one of the next $k$ days all sages will come to the gathering, output a single line containing $-1$. Otherwise, output two lines. The first line contains two integers $d$ and $c$, where $d$ is the earliest day on which some sages do not come to the gathering, and $c$ is the number of sages who do not come on that day. The second line contains $c$ integers: the indices of the sages who do not come, in increasing order.

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

Hint

For $100\%$ of the data, it holds that:

$3\le n, 1\le m, 1\le k\le 30, 1\le a_i<b_i\le n$.

Over all test cases, the sum of $n$ does not exceed $10 ^ 3$, and the sum of $m$ does not exceed $3 \times 10 ^ 3$.

Translated by ChatGPT 5