In the magical land of Bitolandia, $n$ sages have lived for centuries, and $m$ spells exist. According to ancient laws of magic, each spell is known by exactly $n - 2$ sages. All sages know that every spell is known by exactly this many of them, but they do not know exactly how many spells exist. Each sage, for every spell they know, knows exactly which other sages know it. However, they do not know how many spells exist that they do not know. In particular, it may happen that a sage does not know any spells – in that case, they do not know if any spells exist at all (but they still know that if any existed, exactly $n - 2$ sages would know it).

Every day at noon, the sages meet in the Hundred-Megabyte Forest, but they do not talk at all; they simply greet each other and meditate, and at night they all return to their huts. The sages, apart from seeing each other during the meeting, do not communicate with each other in any way. They do this because they fear an ancient tradition that binds them, which states that if a sage learns that there exists a spell they do not know, they must leave for exile at midnight that same night, never to return to Bitolandia.

One day, a traveler arrived in Bitolandia. After a few days of observing the sages, he decided to go to their meeting, where he recklessly announced to them all: "I have noticed that at least one of you knows at least one spell!".

The traveler will remain in Bitolandia for the next $k$ days (at most a month) and will observe the meetings every day, but he will say nothing more. Will there be a day during this time when some sages do not show up for the meeting?

We assume that the sages reason perfectly, i.e., if any of them can deduce something based on the traveler's announcement and the information they possess about the spells, they will certainly do so.

Input

The first line of standard input contains a single positive integer $t$, denoting the number of test cases. The description of subsequent test cases follows according to the format below.

The first line of the test case description contains three integers $n$, $m$, and $k$ ($3 \le n$; $1 \le m$; $1 \le k \le 30$), denoting the number of sages, the number of spells, and the number of subsequent days the traveler will observe the meetings, respectively.

The next $m$ lines of the test case description contain two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$), which denote the existence of a spell that is known by all sages except those numbered $a_i$ and $b_i$ (sages are numbered with integers from $1$ to $n$).

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

Output

The output should contain the answers for all test cases, in the order given in the input.

If in a given test case all sages attend all subsequent $k$ meetings, the answer should consist of a single line containing the number $-1$.

Otherwise, the answer should consist of two lines. The first line should contain two integers $d$ and $c$, where $d$ is the number of the earliest day on which some sages do not come to the meeting, and $c$ is the number of such sages. The second line should contain $c$ integers, denoting the numbers of the sages who will not come to that meeting, arranged in increasing order.

Examples

Input 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

Output 1

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

Note

In the first test case, the second sage does not know any spells, so they will leave on the very first night and will not appear at the first meeting. In the second test case, each sage knows one spell that only they know. When all sages meet at the first meeting, each of them thinks "If the others did not know any spells, they would have left the previous night, and since they are here, they must know spells that I do not!", which causes each of them to leave on the second night and not appear at the second meeting. In the third test case, the sages would not arrive at the second meeting, but the traveler leaves Bitolandia earlier and does not live to see any absences.