Description

The famous gourmet Xiao A is invited to the ATM Grand Hotel to evaluate dishes. The hotel prepares $n$ dishes and numbers them from $1$ to $n$ in decreasing order of estimated quality; dish $1$ has the highest estimated quality.

Due to flavor pairing, some dishes must be prepared before others. Specifically, there are $m$ constraints of the form “dish $i$ must be prepared before dish $j$,” which we abbreviate as $(i, j)$.

Now, the hotel wants to find an optimal preparation order so that Xiao A can eat higher-quality dishes as early as possible:

That is,

1. Subject to all constraints, dish $1$ should be prepared as early as possible.
2. Subject to all constraints and dish $1$ being as early as possible, dish $2$ should be as early as possible.
3. Subject to all constraints and dishes $1$ and $2$ being as early as possible, dish $3$ should be as early as possible.
4. Subject to all constraints and dishes $1$, $2$, and $3$ being as early as possible, dish $4$ should be as early as possible.
5. And so on.

Example 1: There are $4$ dishes with two constraints $(3, 1)$ and $(4, 1)$. Then the preparation order is $3, 4, 1, 2$.

Example 2: There are $5$ dishes with two constraints $(5, 2)$ and $(4, 3)$. Then the preparation order is $1, 5, 2, 4, 3$.

In Example 1, consider dish $1$ first. Because of $(3, 1)$ and $(4, 1)$, dish $1$ can only be prepared after dishes $3$ and $4$ are finished. According to item 3, dish $3$ should be prioritized over dish $4$, so the first three dishes are $3, 4, 1$. Next, consider dish $2$, and the final order is $3, 4, 1, 2$.

In Example $2$, preparing dish $1$ first does not violate any constraints. Next, when considering dish $2$, there is the constraint $(5, 2)$, so prepare $5$ first and then $2$. Next, when considering dish $3$, there is the constraint $(4, 3)$, so prepare $4$ first and then $3$, resulting in the final order $1, 5, 2, 4, 3$. Now you need to compute this optimal preparation order. If there is no solution, output Impossible!.

Input Format

The first line contains a positive integer $t$, the number of test cases. Then follow $t$ test cases. For each test case: The first line contains two space-separated positive integers $n$ and $m$, the number of dishes and the number of precedence constraints. The next $m$ lines each contain two positive integers $x, y$, meaning dish $x$ must be prepared before dish $y$.

Output Format

Output exactly $t$ lines. Each line contains $n$ integers representing the optimal preparation order, or Impossible! if there is no solution.

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

1 5 3 4 2 
Impossible! 
1 5 2 4 3

Hint

• Sample Explanation:

  In the second test case, it simultaneously requires dish $1$ before dish $2$, dish $2$ before dish $3$, and dish $3$ before dish $1$, which is impossible to satisfy, so there is no solution.

• Constraints:

  For $100\%$ of the testdata, $n, m \le 10^5$, $1 \le t \le 3$.

  There may be completely identical constraints among the $m$ constraints.

Translated by ChatGPT 5