B - Who is Saikyo? Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 人の競技プログラマーがいます。順に 人 1, 人 2, \dots, 人 N と呼びます。
競技プログラマーの間には 強さ と呼ばれる関係性があり、相異なる 2 人組 (人 X, 人 Y) 全てに対して 「人 X は人 Y より強い」または「人 Y は人 X より強い」のどちらか一方が成り立ちます。
強さ は 推移律 が成り立ちます。言い換えると、相異なる 3 人組 (人 X, 人 Y, 人 Z) 全てに対して次の条件が成り立ちます。

  • 人 X が人 Y よりも強く、かつ人 Y が人 Z よりも強いとき、人 X は人 Z よりも強い。

人 X が自分以外のどの人 Y に対しても「人 X は人 Y より強い」という関係が成り立つ時、人 X を 最強のプログラマー と呼びます。(上記の制約下においてそのような人がちょうど 1 人存在することが証明できます)

あなたは M 個の強さに関する情報を知っています。i 個目の情報は「人 A_i は人 B_i より強い」という情報です。
あなたは情報を元に N 人の中から最強のプログラマーを特定することができますか？
最強のプログラマーを特定できる場合はその人の番号を出力してください。特定できない場合、つまり最強のプログラマーとしてあり得る人が複数人いる場合は -1 を出力してください。

制約

  • 2 \leq N \leq 50
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
  • 全ての情報が正しくなるように、全ての相異なる 2 人組にどちらが強いかを割り当てる方法が少なくとも 1 通り存在する

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

最強のプログラマーを特定できる場合はその人の番号を出力せよ。特定できない場合は -1 を出力せよ。

入力例 1

3 2
1 2
2 3

出力例 1

1

あなたは「人 1 は人 2 より強い」「人 2 は人 3 より強い」という情報が分かっています。
推移律から「人 1 は人 3 より強い」という情報もわかるので、人 1 は最強のプログラマーです。

入力例 2

3 2
1 3
2 3

出力例 2

-1

最強のプログラマーである可能性がある人は人 1 と人 2 です。最強のプログラマーを一意に特定できないので -1 を出力してください。

入力例 3

6 6
1 6
6 5
6 2
2 3
4 3
4 2

出力例 3

-1

Score : 300 points

Problem Statement

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

  • if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

  • 2 \leq N \leq 50
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
  • There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Input

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

If you can uniquely determine the strongest programmer, print the person's number; otherwise, print -1.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

6 6
1 6
6 5
6 2
2 3
4 3
4 2

Sample Output 3

-1