← 返回题目列表

Codeforces · 645/D

D. 机器人说唱结果报告

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

当农夫约翰在玻维尼亚的一个陌生地区重建他的农场时,贝西正在尝试一些替代工作。在担任记者的新工作中,贝西需要尽快了解编程比赛的结果。当她报道 2016 年机器人说唱比赛时,她注意到所有机器人都在确定性算法下运行。特别是,当且仅当机器人 i 的技能水平高于机器人 j 时,机器人 i 才会击败机器人 j。如果机器人 i 击败机器人 j 并且机器人 j 击败机器人 k,那么机器人 i 将击败机器人 k。由于说唱是一门如此微妙的艺术,两个机器人永远不可能拥有相同的技能水平。

给定说唱战斗的结果(按其进行的顺序),确定贝西可以按技能级别命令所有机器人之前需要进行的第一场说唱战斗的最少数量。

输入

输入的第一行由两个整数组成,机器人数量 n (2 ≤ n ≤ 100 000) 和说唱战斗数量 m ($$1 \leq m \leq \min \left( 100\,000, \frac{n(n-1)}{2} \right)$$)。

接下来的 m 行按照发生的顺序描述说唱比赛的结果。每个由两个整数ui和vi组成(1≤ui,vi≤n,ui≠vi),表示机器人ui在第i次说唱比赛中击败了机器人vi。没有两场说唱大战涉及同一对机器人。

保证机器人的至少一个排序满足所有m个关系。

输出

打印最小 k,以便按技能级别排列机器人的顺序由第一个 k 说唱战斗唯一定义。如果存在多个满足所有 m 个关系的排序,则输出 -1。

示例

输入 #1

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

输出 #1

4

输入 #2

3 2
1 2
3 2

输出 #2

-1

注意

在第一个样本中,从最强到最弱的机器人必须是(4,2,1,3),Bessie 在知道前四场说唱比赛的结果后可以推断出这一点。

在第二个示例中,(1, 3, 2) 和 (3, 1, 2) 都是两次说唱战斗后机器人从最强到最弱的可能排序。