The Worst Reporter

Interview

Time limit1sMemory limit128 MB

Summary

Given some match results of a round-robin where higher-ranked teams always win, find the lexicographically smallest ranking and say whether it is unique.

Level: Medium6 of 10
Topics: Graph, Topological sort, Greedy, Sorting
Solved: No attempts yet

Problem

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.)

Input

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$ .

Output

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.

Examples2

Example 1
Input
```
4
5
1 2
3 1
3 2
3 4
4 1
```
Expected output
```
3
4
1
2
0
```
Example 2
Input
```
3
2
2 1
2 3
```
Expected output
```
2
1
3
1
```