The Worst Reporter

You are a reporter at a newspaper, covering sports.

Up until yesterday, a round-robin league of $n$ soccer teams (every team plays every other team exactly once) took place. Based on the results and the rules, the organizing committee assigned each team a distinct rank from $1$ to $n$. You were told the outcomes of some of the matches, together with the following facts.

• Fact 1: No match ended in a draw.
• Fact 2: Every team received a distinct rank.
• Fact 3: For every $a$, $b$ with $1 \le a < b \le n$, in the match between the team ranked $a$ and the team ranked $b$, the team ranked $a$ always won. (That is, a higher-ranked team always beats a lower-ranked team.)

Using the known match outcomes and Facts 1-3, reconstruct one ranking table consistent with the given information, and also determine whether any ranking table other than the one you output is also consistent with the information.

A ranking table is the list of teams from rank $1$ to rank $n$.

Because several consistent ranking tables may exist, output the lexicographically smallest one. (Compare the sequences of team numbers listed from rank $1$ to rank $n$ and choose the sequence that is smallest in dictionary order.)

The first line contains the number of soccer teams $n$. Each team is numbered from $1$ to $n$.

The second line contains the number of known match outcomes $m$.

Each of the next $m$ lines contains two integers $i$ and $j$ separated by a space, meaning that team $i$ beat team $j$.

The values satisfy $1 \le n \le 5000$ and $1 \le m \le 100000$.

The output consists of $n + 1$ lines.

On lines $1$ through $n$, output a ranking table consistent with the information. On line $i$ ($1 \le i \le n$), output the number of the team ranked $i$. If several ranking tables are consistent, output the lexicographically smallest one.

On line $n + 1$, output an integer indicating whether a ranking table other than the one you output is also consistent with the information. Output $0$ if none exists (the ranking table is unique), or $1$ if one exists.