题目描述

Farmer John 正在 Bovinia 的一片陌生地区重建农场，与此同时，Bessie 正尝试从事一些其他工作。在她作为记者的新工作中，Bessie 需要尽可能快地掌握编程竞赛的结果。

当她报道 2016 年机器人说唱对战锦标赛时，她注意到所有机器人都按照确定性算法运行。具体来说，当且仅当机器人 $i$ 的技能水平高于机器人 $j$ 时，机器人 $i$ 会击败机器人 $j$。此外，如果机器人 $i$ 能击败机器人 $j$，机器人 $j$ 能击败机器人 $k$，那么机器人 $i$ 也一定能击败机器人 $k$。由于说唱是一门非常微妙的艺术，任意两个机器人的技能水平都不相同。

现在按比赛实际发生的顺序给出每一场说唱对战的结果。请确定：Bessie 至少需要知道前多少场对战的结果，才能唯一确定全部机器人按技能水平排列的顺序。

输入格式

第一行包含两个整数 $n$ 和 $m$：

• $n$表示机器人数量；
• $m$（$1\le m\le \min(100\,000,\frac{n(n-1)}2)$）表示说唱对战数量。

接下来的 $m$ 行按照对战发生的先后顺序描述结果。第 $i$ 行包含两个整数 $u_i,v_i$，表示机器人 $u_i$ 在第 $i$ 场对战中击败了机器人 $v_i$。

没有两场对战涉及同一对机器人。保证至少存在一种机器人技能排序满足给出的全部 $m$ 个关系。

输出格式

输出最小的整数 $k$，使得只根据前 $k$ 场对战的结果，就能够唯一确定所有机器人按技能水平排列的顺序。

如果即使使用全部 $m$ 场对战的结果，仍然存在不止一种满足条件的技能排序，则输出 -1。

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

4

说明

机器人从强到弱的顺序必须是 $(4,2,1,3)$。Bessie 在知道前四场说唱对战的结果后就已经可以推断出这一顺序。

3 2
1 2
3 2

-1

说明

在两场对战之后，$(1,3,2)$ 和 $(3,1,2)$ 都可能是机器人从强到弱的顺序，因此无法唯一确定排序。

2 1
1 2

1

数据范围

（$2\le n\le 100\,000$）

（$1\le u_i,v_i\le n$，$u_i\ne v_i$）