問題文

太郎君が$1,2,...,N$という数列を あみだくじ でシャッフルして遊んでいたところ、 あみだくじでシャッフルされた数列を、更に何度か同じあみだくじでシャッフルすると、 元の$1,2,...,N$という数列に戻ることに気が付きました。

例えば次のあみだくじは数列$1,2,3$を$3,1,2$へとシャッフルします。

このあみだくじで数列を更に2回、つまり合計3回シャッフルすることで、数列は元の数列に戻ります。
$1,2,3$ → $3,1,2$ → $2,3,1$ → $1,2,3$

太郎君はあるあみだくじで何度シャッフルを繰り返せば元の数列の戻るのか気になりましたが、 わざわざ手であみだくじを辿っていくのは大変です。 太郎君の代わりに数列$1,2,...,N$を元の数列$1,2,...,N$に戻すために必要な最小のシャッフル回数$S$を計算してあげてください。 ただし、シャッフルは少なくとも1回は行うものとします。

入力

あみだくじは$N$本の縦線と、それに垂直な$K$本の横棒で構成されています。
$K$本の横棒はいずれも異なる高さにあり、上から$k$番目の横棒は、左から$X_k$番目の縦線と 左から$Y_k$番目の縦線を繋いでいます。
数列の$i$番目の数はあみだくじの左から$i$番目の縦線を上から下へと辿っていき、 途中で横棒と接触すると、その横棒と繋がっている縦線へ移動し、また下へとその縦線を辿っていきます。 縦線の一番下へたどり着いたとき、あみだくじの左から$j$番目の縦線にいた場合、 その数は新しくシャッフルされた数列の$j$番目の数になります。

入力は以下の形で与えられます。

$N$
$K$
$X_1$ $Y_1$
$X_2$ $Y_2$
$⋮$
$X_i$ $Y_i$
$⋮$
$X_K$ $Y_K$

1行目には縦棒の数$N$が与えられます。
2行目には横棒の数$K$が与えられます。
3行目から続くK行に、上から$i$番目の横棒が繋ぐ縦線の情報が与えられます。 上から$i$番目の横棒は左から数えて$X_i$番目と$Y_i$番目の縦線をつないでいます。

入力は全て整数で、以下の制約を満たします。
$2\le N\le 100$
$0\le K\le 1000$
$1\le X_i<Y_i\le N$
$X_i+1=Y_i$

出力

$S$

数列$1,2,...,N$を元の数列$1,2,...,N$に戻すために必要な最小のシャッフル回数$S$を1行で出力してください。

サンプル

3
2
2 3
1 2

3

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

2

4
6
1 2
2 3
3 4
3 4
2 3
1 2

1