# Topological orderings P62138

Statement

thehtml

There are n tasks, which have to be done one by one. Some tasks must be done before others: there are m precedence relations between tasks. Write a program that prints all possible ways to order the n tasks according to the m given precedences.

Input

Input consists of a natural number n ≥ 1, followed by a natural number m, followed by m ‍different pairs x, y, indicating that task x must be done before task y. Suppose that the tasks are numbered from 0 to n − 1.

Output

Print, one per line and in lexicographic order, all the ways of sorting the n tasks according to the m given precedences. There will always be at least one solution.

Public test cases
• Input

```3 1
1 0

```

Output

```1 0 2
1 2 0
2 1 0
```
• Input

```1 0
```

Output

```0
```
• Input

```10 18
0 3  4 8
8 3  2 1
5 7  5 6
6 8  4 2
4 0  8 1
2 8  3 1
6 2  7 3
7 2  5 0
0 6  9 5
```

Output

```4 9 5 0 6 7 2 8 3 1
4 9 5 0 7 6 2 8 3 1
4 9 5 7 0 6 2 8 3 1
9 4 5 0 6 7 2 8 3 1
9 4 5 0 7 6 2 8 3 1
9 4 5 7 0 6 2 8 3 1
9 5 4 0 6 7 2 8 3 1
9 5 4 0 7 6 2 8 3 1
9 5 4 7 0 6 2 8 3 1
9 5 7 4 0 6 2 8 3 1
```
• Information
Author