問題文

(1,2,3, \cdots ,N) の順列 P = (P_1,P_2,P_3, \cdots ,P_N) であって、以下の条件を満たすものを K 個求めてください。 K 個存在しない場合は、そのことを報告してください。

• i=1,2,3, \cdots ,M について、順列 P の中で A_i は B_i よりも前にある。

制約

• 1 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 1 \leq K \leq 10
• 1 \leq A_i \leq N
• 1 \leq B_i \leq N
• A_i \neq B_i
• i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
• 入力はすべて整数

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

1. (2 点)： N \leq 10^3
2. (3 点)： K = 1
3. (2 点)： 追加の制約はない。

入力例 1

5 2 3
1 2
3 4

出力例 1

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

この入力例は小課題 1,3 のみの制約を満たします。

順列 P の条件は

• 1 が 2 よりも前にある
• 3 が 4 よりも前にある

の 2 つを両方満たすことです。

この条件を満たす相異なる K 個の順列であれば、出力例と異なる順列を出力しても正解となります。また、 K 個の順列を出力する順番が異なっていても正解となります。

入力例 2

5 2 1
1 3
3 1

出力例 2

-1

この入力例はすべての小課題の制約を満たします。

条件を満たす順列は 1 つも存在しません。

入力例 3

10 15 10
8 4
9 4
10 2
6 2
10 6
1 3
7 4
6 8
8 1
5 6
10 9
3 7
8 3
3 9
2 3

出力例 3

5 10 6 2 8 1 3 7 9 4
5 10 6 2 8 1 3 9 7 4
5 10 6 8 2 1 3 7 9 4
5 10 6 8 2 1 3 9 7 4
5 10 6 8 1 2 3 7 9 4
5 10 6 8 1 2 3 9 7 4
10 5 6 2 8 1 3 7 9 4
10 5 6 2 8 1 3 9 7 4
10 5 6 8 2 1 3 7 9 4
10 5 6 8 2 1 3 9 7 4

この入力例は小課題 1,3 のみの制約を満たします。