#K33737. Game Ranking Algorithm

    ID: 25154 Type: Default 1000ms 256MiB

Game Ranking Algorithm

Game Ranking Algorithm

In this problem, you are given a tournament of \(n\) players and \(m\) games. Each game result is represented by a pair of integers \(u\) and \(v\), which means that player \(u\) defeated player \(v\) (i.e. \(u \to v\)). Your task is to determine a ranking of the players, i.e. a permutation of \(\{1,2,\ldots,n\}\), such that if player \(u\) defeated player \(v\), then \(u\) appears before \(v\) in the ranking.

If no such ranking exists (due to cycles in the match results), output IMPOSSIBLE. In the absence of any game results, output the players in increasing order.

This problem can be solved by performing a topological sort on the directed graph defined by the match outcomes.

inputFormat

The first line of input contains two integers \(n\) and \(m\), where \(n\) is the number of players and \(m\) is the number of games played.

The next \(m\) lines each contain two integers \(u\) and \(v\) (separated by a space), indicating that player \(u\) has defeated player \(v\).

You should read from stdin.

outputFormat

If a valid ranking exists, output a single line containing the ranking as space-separated integers.

If no valid ranking exists, output a single line with the word IMPOSSIBLE.

Write your answer to stdout.

## sample
5 4
1 2
3 2
4 2
5 3
1 4 5 3 2

</p>