Until now you would have known that Maggu is a big geek. His class has n students. All the students are geeks like him. You are given m information of form a, b which denotes that a'th guy is less geeky than b'th guy (geekiness(a) < geekiness (b)). Note that geekiness of each person is unique and can be from 1 to n. Now Maggu wonders what are the possible values of his geekiness. If such a distribution of geekiness value is not possible, then output -1.

Input

First line contains T: number of test cases (1 ≤ T ≤ 100).

For each test case, first line contains n, m, idx where n is number of boys in the class, m is number of information, idx is the index corresponding to Maggu. 1 ≤ n ≤ 10⁶, 1 ≤ m ≤ min (10⁵, n × (n - 1) / 2), 1 ≤ idx ≤ n.

Then next m line contains two space separated integers representing a, b. (1 ≤ a, b ≤ n).

No pair of information is repeated twice in the input.

Output

For each test case, You have to output one or two lines depending on the situation. In the former case, If the distribution of geekiness can not exist, output -1.

In the second case (i.e. two lines), In the first line, output a single integer number of possible geekiness values of Maggu. Then in the next line output in the increasing order all the possible geekiness values of Maggu in ascending order. All the values should be space separated.

Example

Input:
2
3 2 1
1 2
2 3
4 2 1
1 2
3 4

Output:
1
1
3
1 2 3