#K33737. Game Ranking Algorithm
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.
## sample5 4
1 2
3 2
4 2
5 3
1 4 5 3 2
</p>