P1960 The Frustrated Reporter

You are a reporter for a sports newspaper, and you have received a challenging task: there are $N$ football teams participating in a tournament. You are given some match results and need to output the ranking of all teams from $1$ to $N$. The following information applies: 1. There are no draws. 2. Different teams cannot share the same rank. 3. For all $1 \le a < b \le N$, the team in position $a$ must be able to defeat the team in position $b$. Given partial match results, output one valid ranking, and determine whether there exists another ranking that also satisfies the given results.

The first line contains $N$, the number of teams, numbered from $1$ to $N$. The second line contains $M$, the number of given matches. Each of the next $M$ lines contains two integers $X_i$, $Y_i$, meaning team $X_i$ can defeat team $Y_i$.

Output $N+1$ lines. The first $N$ lines describe the ranking of the teams: the $i$-th line contains the team ranked $i$-th. The $(N+1)$-th line contains one integer; output $0$ if there is no other ranking that satisfies the given results, or $1$ if there is at least one other valid ranking.

Constraints - $30\%$ of the testdata satisfies: $1 \le N \le 7$, $1 \le M \le 15$. - $60\%$ of the testdata satisfies: $1 \le N \le 100$, $1 \le M \le 2 \times 10^3$. - $100\%$ of the testdata satisfies: $1 \le N \le 5 \times 10^3$, $1 \le M \le 10^5$. This problem uses `Special Judge`. - If the last line is incorrect, the message will be `Your decide is wrong!`. - If multiple rankings are possible and your ranking is wrong, the message will be `Wrong ranks!`. - If the ranking is unique and your answer is wrong, the message will be `In line X,Your ans is wrong:expected = X,found = Y`. Translated by ChatGPT 5