Tournament

Time limit1sMemory limit128 MB

Summary

Given a partial tournament (a directed acyclic graph), produce the valid topological order that is lexicographically smallest when read from highest rank to lowest.

Level: Hard8 of 10
Topics: Graph, Topological sort, Greedy, Heap
Solved: No attempts yet

Problem

A tournament was held with $n$ competitors. The competitors are numbered from $1$ to $n$ in the order they registered. The plan was to play one match between every pair of competitors, but a strong wind interrupted the tournament after only some of the matches had been played. Because the awards ceremony could not be postponed, the jury still has to assign a final ranking, and no two competitors may share the same place.

To build the ranking, the head judge fixed this rule:

Every competitor must be placed strictly higher in the ranking than every competitor they beat in a head-to-head match.

Many rankings can satisfy this rule, so the head judge also fixed a way to compare two rankings:

Ranking $A$ is better than ranking $B$ if, at the highest position where the two rankings differ, ranking $A$ places a competitor who registered earlier (that is, has a smaller number).

Produce the best possible ranking. The matches played so far guarantee that at least one valid ranking exists.

Input

The first line contains two integers $n$ and $m$ separated by a single space ( $2 \le n \le 100000$ , $0 \le m \le 100000$ ), where $n$ is the number of competitors and $m$ is the number of matches played. Each of the next $m$ lines describes one match with two integers separated by a single space: the number of the winner, followed by the number of the loser.

Output

Print the best ranking: the competitors' numbers from the highest position down to the lowest, one number per line.

Examples3

Example 1

Input

Expected output

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