Description

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.

Input Format

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 Format

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.

3
2
2 1
2 3

2
1
3
1

Hint

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