Score : $300$ points

问题描述

有 $N$ 名竞赛程序员，编号分别为 person 1、person 2、…、person $N$。

在这些程序员之间存在一种称为“优势”的关系。对于任意一对不同的程序员（person $X$ 和 person $Y$），恰好满足以下两种关系之一：“person $X$ 比 person $Y$ 更强”或“person $Y$ 比 person $X$ 更强”。

这种优势关系具有传递性。换句话说，对于所有三元组不重复的程序员（person $X$、person $Y$ 和 person $Z$），满足以下条件：

• 如果 person $X$ 比 person $Y$ 更强且 person $Y$ 比 person $Z$ 更强，那么 person $X$ 比 person $Z$ 更强。

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

你手头有关于他们优势关系的 $M$ 条信息。第 $i$ 条信息是：“person $A_i$ 比 person $B_i$ 更强”。

你能根据这些信息确定这 $N$ 名程序员中的最强程序员吗？
如果可以，请输出该程序员的编号。否则，即如果有多个可能的最强程序员时，请输出 -1。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:55:03