問題文

$N$ 行 $N$ 列の行列 $A$ があります。$i=1,2,\ldots,K$ に対し $A$ の $r_i$ 行 $c_i$ 列成分は $1$ で、それ以外の成分は $0$ です。

$A^m$ が零行列となるような正の整数 $m$ が存在するかを判定し、存在するときは $m$ の最小値を求めてください。

制約

• $1\le N\le 10^5$
• $0\le K\le \min(N^2,10^5)$
• $1\le r_i,c_i\le N$
• $i\ne j$ ならば $(r_i,c_i)\ne (r_j,c_j)$
• 入力はすべて整数

入力

$N$ $K$
$r_1$ $c_1$
$r_2$ $c_2$
$\vdots$
$r_K$ $c_K$

出力

$A^m$ が零行列となるような正の整数 $m$ が存在するときは、$m$ の最小値を出力してください。存在しないときは $-1$ を出力してください。

サンプル

3 3
1 2
1 3
2 3

3

3 3
1 1
2 2
3 3

-1

1 0

1