Who is Saikyo?

题目描述

共有 $N$ 位编号为 person $1$、person $2$、$\ldots$、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$ 强。

若对所有除 person $X$ 自身之外的人 $Y$，person $X$ 都比 person $Y$ 强，则称 person $X$ 为 最强的程序员。（在上述约束下，可以证明恰好存在这样一位程序员。）
你得到了关于他们优越性的 $M$ 条信息。第 $i$ 条信息是“person $A_i$ 比 person $B_i$ 强”。
能否基于这些信息确定 $N$ 人中谁是最强的程序员？
如果能，输出该人的编号；否则，也就是存在多个可能的最强程序员时，输出 $-1$。

输入格式

输入由标准输入按以下格式给出： $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

输出格式

如果能唯一确定最强的程序员，则输出该人的编号；否则，输出 $-1$。

3 2
1 2
2 3

1

3 2
1 3
2 3

-1

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

-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)$。 存在至少一种方式可以为所有不同的程序员对确定优越性，且该方式与已给信息一致。你有两条信息：“person $1$ 比 person $2$ 强”和“person $2$ 比 person $3$ 强”。
由传递性，你还可以推断出“person $1$ 比 person $3$ 强”，因此 person $1$ 是最强的程序员。
person $1$ 和 person $2$ 都有可能是最强的程序员。由于你不能唯一确定最强者，所以应输出 $-1$。

标签: AtCoder|abc313B

来源

AtCoder|abc313B