Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2025. december 7.

December 7, 2025, 10:30 AM – December 7, 2025, 3:30 PM

permutation-1

We have NN tasks labeled with numbers 1,…,N1,\ldots,N. For certain task pairs (akbk,k=1,…,Ma_k b_k,~~k=1,\ldots,M), we know that one task (aka_k) must be completed before we start the other (bkb_k). Considering all valid orderings satisfying the given conditions in lexicographic order, find the KK-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 TT, the number of test cases. Then TT test cases follow. Description of a test case: First line: three numbers NMKN~~ M~~ K. Next MM lines: numbers akbk(k=1,…,M)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≤T≤1001\le T \le 100
1≤N≤1_0001\le N \le 1\_000
0≤M≤1_0000\le M \le 1\_000
1≤K≤1_0001\le K \le 1\_000
1≤ak≤1_0001\le a_k \le 1\_000
1≤bk≤1_0001\le b_k \le 1\_000
ak≠bka_k\neq b_k 1≤ak,bk≤N1\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
download as text file

Sample output 1

  1. 2 1 3 4
  2. 3 2 1 4
  3. -1
  4. -1
download as text file
University of Debrecen; Faculty of Informatics; v. 09/30/2024