谁是最强

题目描述

有 $N$ 名竞技程序员,分别称为第 $1$ 人、第 $2$ 人、$\dots$、第 $N$ 人。 程序员之间存在一种名为「强弱」的关系,对于任意一对不同的人 $($第 $X$ 人、第 $Y$ 人$)$,「第 $X$ 人比第 $Y$ 人强」与「第 $Y$ 人比第 $X$ 人强」两者中恰好有一方成立。 「强弱」关系满足传递律。换言之,对于任意三个不同的人 $($第 $X$ 人、第 $Y$ 人、第 $Z$ 人$)$,以下条件成立:

如果第 $X$ 人比第 $Y$ 人强,且第 $Y$ 人比第 $Z$ 人强,则第 $X$ 人比第 $Z$ 人强。

当第 $X$ 人比除自己以外的任何第 $Y$ 人都强时,称第 $X$ 人为最强程序员。(在上述约束下,可以证明这样的人恰好存在 1 人。) 你已知 $M$ 条关于强弱关系的信息,其中第 $i$ 条信息是「第 $A_i$ 人比第 $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

已知「第 $1$ 人比第 $2$ 人强」和「第 $2$ 人比第 $3$ 人强」两条信息。 由传递律还可以推出「第 $1$ 人比第 $3$ 人强」,因此第 $1$ 人是最强程序员。

3 2
1 3
2 3

-1

第 $1$ 人和第 $2$ 人都可能是最强程序员。由于无法唯一确定谁是最强,应输出 $-1$。

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

-1

数据范围

• $2 \le N \le 50$
• $0 \le M \le \frac{N(N-1)}{2}$
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• 若 $i \neq j$,则 $(A_i, B_i) \neq (A_j, B_j)$
• 存在至少一种对所有不同的两人对分配强弱关系的方法,使得所有信息都成立