G - Round Robin Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

1 から N までの番号がついた N 人が総当たり戦をしています。
すなわち、全ての組 (i,j) (1\leq i \lt j \leq N) について、人 i と人 j は 1 回試合をするので、試合は合計で \frac{N(N-1)}{2} 試合行われます。
なお、試合は必ず一方が勝者、もう一方が敗者となり、引き分けとなることはありません。

既に M 試合が終了しており、i 試合目では人 W_i が人 L_i に勝ちました。

総当たり戦が終了したとき、単独優勝をする可能性のある人を列挙してください。
ただし単独優勝とは、その人の勝利数が、他のどの人の勝利数よりも多いことを言います。

制約

  • 2\leq N \leq 50
  • 0\leq M \leq \frac{N(N-1)}{2}
  • 1\leq W_i,L_i\leq N
  • W_i \neq L_i
  • i\neq j ならば、(W_i,L_i) \neq (W_j,L_j)
  • (W_i,L_i) \neq (L_j,W_j)
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
W_1 L_1
W_2 L_2
\vdots
W_M L_M

出力

単独優勝をする可能性のある人の番号の集合を A=(A_1,A_2,\dots,A_K) (A_1\lt A_2 \lt \dots \lt A_K) として、A を昇順に空白区切りで出力せよ。
すなわち、以下の形式で出力せよ。 

A_1 A_2 \dots A_K

入力例 1

4 2
2 1
2 3

出力例 1

2 4

人 2,4 は単独優勝する可能性があり、人 1,3 は単独優勝する可能性がありません。
なお、4 2 などの出力は不正解となることに注意してください。

入力例 2

3 3
1 2
2 3
3 1

出力例 2



単独優勝する可能性のある人がいないこともあります。













入力例 3
7 9
6 5
1 2
3 4
5 3
6 2
1 5
3 2
6 4
1 4












出力例 3
1 3 6 7







Score : 600 points







Problem Statement
N players numbered 1 through N will participate in a round-robin tournament.

Specifically, for every pair (i,j) (1\leq i \lt j \leq N), Player i and Player j play a match against each other once, for a total of \frac{N(N-1)}{2} matches.

In every match, one of the players will be a winner and the other will be a loser; there is no draw.


M matches have already ended.  In the i-th match, Player W_i won Player L_i.  


List all the players who may become the unique winner after the round-robin tournament is completed.

A player is said to be the unique winner if the number of the player's wins is strictly greater than that of any other player.











Constraints
    

  • 2\leq N \leq 50
    • 

  • 0\leq M \leq \frac{N(N-1)}{2}
    • 

  • 1\leq W_i,L_i\leq N
    • 

  • W_i \neq L_i
    • 

  • If i\neq j, then (W_i,L_i) \neq (W_j,L_j).
    • 

  • (W_i,L_i) \neq (L_j,W_j)
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N M
W_1 L_1
W_2 L_2
\vdots
W_M L_M












Output
Let A=(A_1,A_2,\dots,A_K) (A_1\lt A_2 \lt \dots \lt A_K) be the set of indices of players that may become the unique winner.  Print A in the increasing order, with spaces in between.

In other words, print in the following format.  


A_1 A_2 \dots A_K
















Sample Input 1
4 2
2 1
2 3












Sample Output 1
2 4



Players 2 and 4 may become the unique winner, while Players 1 and 3 cannot.

Note that output like 4 2 is considered to be incorrect.  













Sample Input 2
3 3
1 2
2 3
3 1












Sample Output 2


It is possible that no player can become the unique winner.













Sample Input 3
7 9
6 5
1 2
3 4
5 3
6 2
1 5
3 2
6 4
1 4












Sample Output 3
1 3 6 7