CF645D.Robot Rapping Results Report

While Farmer John rebuilds his farm in an unfamiliar portion of Bovinia, Bessie is out trying some alternative jobs. In her new gig as a reporter, Bessie needs to know about programming competition results as quickly as possible. When she covers the 2016 Robot Rap Battle Tournament, she notices that all of the robots operate under deterministic algorithms. In particular, robot i will beat robot j if and only if robot i has a higher skill level than robot j. And if robot i beats robot j and robot j beats robot k, then robot i will beat robot k. Since rapping is such a subtle art, two robots can never have the same skill level.

Given the results of the rap battles in the order in which they were played, determine the minimum number of first rap battles that needed to take place before Bessie could order all of the robots by skill level.

当农夫约翰在波维尼亚（Bovinia）一个陌生的区域重建他的农场时，贝茜外出尝试一些替代性工作。在她担任记者的新工作中，贝茜需要尽快了解编程竞赛的结果。当她报道2016年机器人说唱对决锦标赛（Robot Rap Battle Tournament）时，她注意到所有机器人都遵循确定性算法运行。具体而言，当且仅当机器人 $i$ 的技能等级高于机器人 $j$ 时，机器人 $i$ 才能击败机器人 $j$；并且若机器人 $i$ 击败机器人 $j$、机器人 $j$ 击败机器人 $k$，则机器人 $i$ 必定击败机器人 $k$。由于说唱是一门极为精妙的艺术，任意两个机器人的技能等级都不可能相同。

给定说唱对决的结果（按比赛进行的先后顺序给出），请确定：在贝茜能够将所有机器人按技能等级完全排序之前，最少需要进行多少场最初的说唱对决。

The first line of the input consists of two integers, the number of robots n (2 ≤ n ≤ 100 000) and the number of rap battles m ().

The next m lines describe the results of the rap battles in the order they took place. Each consists of two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i), indicating that robot u__i beat robot v__i in the i-th rap battle. No two rap battles involve the same pair of robots.

It is guaranteed that at least one ordering of the robots satisfies all m relations.

输入的第一行包含两个整数：机器人数量 $n$（$2 \leq n \leq 100\,000$）和说唱对决次数 $m$（）。

接下来的 $m$ 行按发生顺序描述每场说唱对决的结果。每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$），表示在第 $i$ 场说唱对决中，机器人 $u_i$ 击败了机器人 $v_i$。任意两场说唱对决所涉及的机器人对均不相同。

保证至少存在一种机器人的排列顺序，能够满足全部 $m$ 个关系。

Print the minimum k such that the ordering of the robots by skill level is uniquely defined by the first k rap battles. If there exists more than one ordering that satisfies all m relations, output -1.

输出最小的 k，使得机器人按技能水平排序的结果能被前 k 场说唱对决唯一确定。如果存在多于一种排序方式满足全部 m 个关系，则输出 -1。

In the first sample, the robots from strongest to weakest must be (4, 2, 1, 3), which Bessie can deduce after knowing the results of the first four rap battles.

In the second sample, both (1, 3, 2) and (3, 1, 2) are possible orderings of the robots from strongest to weakest after both rap battles.

在第一个样例中，机器人从最强到最弱的顺序必为 $(4,\,2,\,1,\,3)$，贝茜在得知前四场说唱对决的结果后即可推断出该顺序。

在第二个样例中，在两场说唱对决结束后，$(1,\,3,\,2)$ 和 $(3,\,1,\,2)$ 均可能是机器人从最强到最弱的可能顺序。