AT_abc313_b [ABC313B] Who is Saikyo?

题目描述

有 $N$ 名竞赛程序员，依次编号为第 $1$ 个人、第 $2$ 个人，……，第 $N$ 个人。
在竞赛程序员之间存在一种称为强度的关系，对于任意不同的两个人 $(X, Y)$，总有“第 $X$ 个人比第 $Y$ 个人强”或“第 $Y$ 个人比第 $X$ 个人强”其中之一成立。
强度关系满足传递性。换句话说，对于任意不同的三个人 $(X, Y, Z)$，有如下条件成立：

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

如果对于任意其他人 $Y$，都有“第 $X$ 个人比第 $Y$ 个人强”成立，则称第 $X$ 个人为最强程序员。（在上述约束下，可以证明恰好存在一名这样的人。）

你知道 $M$ 条关于强度的信息。第 $i$ 条信息是“第 $A_i$ 个人比第 $B_i$ 个人强”。
你能根据这些信息在 $N$ 个人中确定最强程序员吗？
如果可以确定，请输出该人的编号。如果无法确定（即有多个人可能是最强程序员），请输出 -1。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

如果能够确定最强程序员，请输出其编号。如果无法确定，请输出 -1。

输入输出样例 #1

输入 #1

3 2
1 2
2 3

输出 #1

1

输入输出样例 #2

输入 #2

3 2
1 3
2 3

输出 #2

-1

输入输出样例 #3

输入 #3

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

输出 #3

-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)$
• 至少存在一种分配方式，使得所有信息都成立，并且对于每一对不同的两个人都能确定谁更强。

样例解释 1

你知道“第 $1$ 个人比第 $2$ 个人强”、“第 $2$ 个人比第 $3$ 个人强”。由传递性可知“第 $1$ 个人比第 $3$ 个人强”，因此第 $1$ 个人是最强程序员。

样例解释 2

有可能成为最强程序员的人是第 $1$ 个人和第 $2$ 个人。无法唯一确定最强程序员，因此请输出 -1。

由 ChatGPT 4.1 翻译