103131: [Atcoder]ABC313 B - Who is Saikyo?

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

问题描述

有$N$个竞争激烈的程序员，编号为第1人，第2人，$\ldots$，第$N$人。

程序员之间有一种称为优越的关系。 对于所有不同的程序员对$(X$人，$Y$人$)$，以下两种关系之一成立：“$X$人比$Y$人强”或“$Y$人比$X$人强”。

优越性是传递的。 换句话说，对于所有不同的程序员三元组$(X$人，$Y$人，$Z$人$)$，都满足以下条件：

• 如果$X$人比$Y$人强，且$Y$人比$Z$人强，则$X$人比$Z$人强。

称$X$人为最强程序员，如果对于除$X$人以外的所有人$Y$，都有$X$人比$Y$人强。 （根据上述条件，我们可以证明总是存在一个这样的人。）

你有$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)$。
• 至少有一种方法可以确定所有不同程序员对之间的优越性，这与给定信息一致。

输入

输入将从标准输入以以下格式给出：

$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