問題文

$N$ 頂点 $0$ 辺のグラフがあり、このグラフに $Q$ 回の操作を行います。 $i$ 回目の操作では、 $A_i$ から $B_i$ への有向辺を追加します。

$Q$ 回の操作を順に行っていったとき、グラフに最初に閉路ができるのはいつか出力してください。厳密には、 $j(1\leq j\leq i)$ 回目の操作を行ったときグラフに閉路が存在するような最小の $i$ を出力してください。
ただし、そのような $i$ が存在しない場合は $-1$ を出力してください。

入力

$N$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

• 入力はすべて整数
• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq Q)$
• $A_i \neq B_i$ $(1 \leq i \leq Q)$

出力

最後に改行してください。

サンプル

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

4

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

-1

16 20
2 6
8 1
2 5
12 8
4 11
15 12
9 13
9 12
8 7
12 11
8 10
14 8
15 14
16 3
15 12
15 11
15 13
3 16
1 7
5 6

18

33 4
33 4
33 4
33 4
33 4

-1