permutation-1

Van $N$ feladat melyek az $1,\ldots,N$ számokkal vannak jelölve. Bizonyos feladatpárokról ($a_k b_k,~~k=1,\ldots,M$) tudjuk hogy az egyiket ($a_k$) mindenképpen el kell végeznünk mielőtt belekezünk a másikba ($b_k$). Az adott feltételeket kielégítő sorrendeket lexikografikus sorrendben elképzelve, keressük a $K$-adikat. Például legyen $N=4$ $M=3$ és $K=2,4$

Az adott sorrendek:
4 1
4 2
2 3

Ekkor az összes lehetséges elrendezés lexikografikus sorrendbe rakva:

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

Látható, hogy a 4 2 1 3 a második és az világos is hogy nincsen negyedik a megfelelő sorrendek közt.

Bemenet specifikáció

Az első sorban $T$ az esetek száma. Ezután $T$ eset következik. Egy eset leírása: Az első sorban három szám: $N~~ M~~ K$. A következő $M$ sorban az $a_k b_k~~(k=1,\ldots,M)$ számok vannak. Egy számpár legfeljebb egyszer szerepel a listában.

Kimenet specifikáció

$T$ lines, each containing the requested permutation or “-1”.

Korlátok

$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$

1. példa bemenet

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

1. példa kimenet

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