Maximum Temperature Assignment

You are given n days and k comparisons. Each comparison is a pair of integers (a, b) which indicates that the temperature on day a is strictly higher than the temperature on day b. Your task is to assign a unique temperature from the set \(\{1, 2, \dots, n\}\) to each day such that all the comparisons are satisfied.

If there exists a valid assignment, output any one of them. In particular, one common approach is to perform a topological sort on the directed graph defined by the comparisons and then assign temperatures in a way that the first day in the topological order receives the highest temperature and so on. Formally, if the topological order is \(d_1, d_2, \dots, d_n\), then assign

[ T(d_i) = n-i+1,\quad \text{for } 1 \le i \le n. ]

If it is impossible to find a valid ordering (i.e. the graph contains a cycle), output -1.

Note: When there are no comparisons, any permutation of \(\{1, 2, \dots, n\}\) is acceptable since they all satisfy the (empty) set of constraints.

inputFormat

The input is given from the standard input (stdin) in the following format:

T
n1 k1
a1 b1
... (k1 lines of comparisons)
n2 k2
... (k2 lines of comparisons)
...

Here, T is the number of test cases. For each test case, the first line contains two integers: n (the number of days) and k (the number of comparisons). This is followed by k lines, each containing two integers a and b indicating that day a must have a higher temperature than day b.

outputFormat

For each test case, print a single line to standard output (stdout). If a valid temperature assignment exists, output n integers representing the assigned temperatures for days 1 through n respectively, separated by spaces. If no valid assignment exists, print -1.

## sample

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

1 0

2 1
1 2

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

</p>