← 返回题目列表

AtCoder · abc313_b

D. 西京是谁?

中文机器翻译题面 查看原题

分数: 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