Wise Men

In the magical land of Bitolandia, $n$ wise men have lived for ages, and there are $m$ spells. Under the ancient laws of magic, each spell is known by exactly $n-2$ wise men. All the wise men know this, but none of them knows how many spells exist. Each wise man knows, for every spell he knows, exactly which other wise men know it. He does not know how many spells he does not know. A wise man who knows no spells does not know whether any spells exist at all, though he does know that if one existed, exactly $n-2$ wise men would know it.

Every day at noon the wise men meet in the Hundred-Megabyte Forest. They do not talk. Each one greets every other one and then they meditate, and at night everyone returns to their hut. Apart from seeing each other at these meetings, the wise men have no way of communicating. They are careful because of an old tradition: if a wise man learns that a spell exists which he does not know, he must quietly leave Bitolandia at midnight on the following night and never return.

One day a wanderer arrived in Bitolandia. After several days of watching the wise men, he went to their meeting and announced to all of them: "I have noticed that at least one of you knows at least one spell!"

The wanderer will stay in Bitolandia for another $k$ days (at most a month) and will watch every meeting, but he will say nothing more. Will there be a day during that time when some of the wise men do not show up at the meeting?

Assume the wise men reason perfectly. If one of them can deduce something from the wanderer's announcement and from what he knows about the spells, he will certainly do so.

The first line contains a single integer $t$, the number of test cases. Each test case follows.

The first line of a test case contains three integers $n$, $m$, and $k$ ($3 \le n$; $1 \le m$; $1 \le k \le 30$), which are the number of wise men, the number of spells, and the number of further days the wanderer will watch the meetings.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$), meaning that there is a spell known by all wise men except those numbered $a_i$ and $b_i$. The wise men are numbered from $1$ to $n$.

It is guaranteed that the sum of $n$ over a file does not exceed 1000, and the sum of $m$ over a file does not exceed 3000.

If all wise men attend all $k$ meetings that the wanderer observes, print a single line containing $-1$.

Otherwise, print two lines. The first line contains two integers $d$ and $c$, where $d$ is the number of the earliest day on which some wise men do not attend the meeting, and $c$ is the number of wise men who do not attend that day. The second line contains the $c$ numbers of those wise men in increasing order.

In the first test case, the second wise man knows no spells, so he leaves on the first night and does not appear at the first meeting. In the second test case, each wise man knows one spell that only he knows. When all of them meet at the first meeting, each thinks: "If the others knew no spells, they would have left the night before. Since they are here, they must know spells that I do not know!" So all of them leave on the second night and miss the second meeting. In the third test case, the wise men would not reach the second meeting, but the wanderer leaves Bitolandia before that, so no absence is ever observed.