P3243 [HNOI2015] Dish Preparation

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!`.

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 exactly $t$ lines. Each line contains $n$ integers representing the optimal preparation order, or `Impossible!` if there is no solution.

- 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