分数: 300 点
问题陈述
有 N 竞争程序员人数 1, 人 2, \ldots和人 N.
有一个关系叫做 优越性 程序员之间。 对于所有不同的程序员对 (人 X, 人 Y),恰好满足以下两个关系之一:“人 X 比人强 Y“或”人 Y 比人强 X."
优越性是 及物。 换句话说,对于不同程序员的所有三胞胎 (人 X, 人 Y, 人 Z),认为:
- 如果人 X 比人强 Y 和人 Y 比人强 Z,然后人 X 比人强 Z.
一个人 X 据说是 最强程序员 如果人 X 比人强 Y 适合所有人 Y 人以外 X。 (在上述约束下,我们可以证明这样的人总是存在的。)
你有 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
- If 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