permutation-1

We have $N$ tasks labeled with numbers $1,\ldots,N$. For certain task pairs ($a_k b_k,~~k=1,\ldots,M$), we know that one task ($a_k$) must be completed before we start the other ($b_k$). Considering all valid orderings satisfying the given conditions in lexicographic order, find the $K$-th ordering. For example, let N=4, M=3, and K=2,4:

The given orders:
4 1
4 2
2 3

Then all possible orderings in lexicographic order:

4 1 2 3
4 2 1 3
4 2 3 1

We can see that 4 2 1 3 is the second, and also clear that there is no fourth valid ordering.

Input specification

The first line contains $T$, the number of test cases. Then $T$ test cases follow. Description of a test case: First line: three numbers $N~~ M~~ K$. Next $M$ lines: numbers $a_k b_k~~(k=1,\ldots,M)$. Each pair appears at most once in the list.

Output specification

T lines with the…

Constraints

$1\le T \le 100$
$1\le N \le 1\_000$
$0\le M \le 1\_000$
$1\le K \le 1\_000$
$1\le a_k \le 1\_000$
$1\le b_k \le 1\_000$
$a_k\neq b_k$ $1\le a_k,b_k \le N$

Sample input 1

1. 4
2. 4 3 1
3. 2 1
4. 3 4
5. 2 4
6. 4 3 4
7. 2 1
8. 3 4
9. 2 4
10. 4 3 8
11. 2 1
12. 3 4
13. 2 4
14. 4 4 5
15. 1 2
16. 2 3
17. 3 4
18. 4 2

Sample output 1

1. 2 1 3 4
2. 3 2 1 4
3. -1
4. -1