Valid Toy Arrangement

You are given a set of N toys, numbered from 1 to N. There are K ordering constraints provided as pairs of integers. Each constraint \( (X, Y) \) means that toy \( X \) must appear before toy \( Y \) in the arrangement.

Your task is to determine a valid sequence of toys that satisfies all the given constraints. If multiple valid sequences exist, output the one obtained by the following procedure:

• For all toys that have no prerequisites (i.e. in-degree equal to 0), add them to a queue in increasing order.
• Then, repeatedly remove a toy from the front of the queue and append it to the sequence. Decrease the in-degree of all toys that depend on the removed toy. If any of these toys now has an in-degree of 0, add them to the queue.

If it is impossible to arrange the toys (i.e. a cycle exists), output No valid arrangement.

Note: In this problem, the in-degree of a toy \( i \) is defined as \( \text{inDegree}(i) = \#\{ j : (j, i) \text{ is a constraint}\} \).

inputFormat

The input is given via stdin and has the following format:

T
N K
X1 Y1
X2 Y2
... (K lines)
... (repeat for T test cases)

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers \( N \) (the number of toys) and \( K \) (the number of constraints).
• Then, \( K \) lines follow, each containing two integers \( X \) and \( Y \) representing a constraint that toy \( X \) should come before toy \( Y \).

outputFormat

For each test case, output a single line via stdout:

• If a valid ordering exists, output the ordering of toys as space-separated integers.
• If no valid ordering exists, output No valid arrangement.

## sample

2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

1 2 3
No valid arrangement

</p>