9846번 - Rank 다국어

In a new sports discipline called Triball proposed for the Youth Olympic Games in Singapore, a set of k players {1, 2, . . . , k} are involved (where k < 1000). In every match, 3 players are selected and the result of the match is either 1 winner or 1 loser. Given the result of n matches (where n < 10000), our task is to give a ranking list of the players.

Precisely, the i^th match involves three distinct players p_i1, p_i2, p_i3 ∈ {1, 2, . . . , k}. The result of the i th match is represented by p_i1 > p_i2, p_i3 (or p_i2, p_i3 > p_i1) where p_i1 is the winner (or loser) of the match. The result p_i1 > p_i2, p_i3 implies that p_i1 is better than p_i2 and that p_i1 is better than p_i3. Similarly, the result p_i2, p_i3 > p_i1 implies that p_i2 is better than p_i1 and that p_i3 is better than p_i1. Our aim is to find the permutation of the k players so that a better player always comes before his opponent, considering all given matches. If we cannot reach our aim and such a permutation does not exist, we output 0.

The input is as follows. The first line contains two integers k and n separated by a space character, where 1 ≤ k ≤ 1000, 1 ≤ n ≤ 10000. The number k is the number of players, denoted by numbers from 1 to k. The remaining n lines contain n results in the form of either p_i1 > p_i2, p_i3 or p_i2, p_i3 > p_i1.

If there is a valid ranking of the players, the output contains k integers, separated by a space character, representing the ordering of the players. Otherwise, the output contains one integer 0.