Problem Statement

While Taro was playing by shuffling the sequence $1, 2, ... , N$ using amidakuji , he noticed that if a sequence shuffled by an amidakuji is shuffled several more times with the same amidakuji, it returns to the original sequence $1, 2, ... , N$.

For example, the following amidakuji shuffles the sequence $1, 2, 3$ into $3, 1, 2$.

By shuffling the sequence 2 more times with this amidakuji, that is, 3 times in total, the sequence returns to the original sequence.
$1, 2, 3$ → $3, 1, 2$ → $2, 3, 1$ → $1, 2, 3$

Taro wondered how many times the shuffle must be repeated with a given amidakuji for the sequence to return to the original, but tracing the amidakuji by hand is tedious. On Taro's behalf, compute the minimum number of shuffles $S$ required to return the sequence $1, 2, ... , N$ to the original sequence $1, 2, ... , N$. Note that the shuffle must be performed at least once.

Input

The amidakuji consists of $N$ vertical lines and $K$ horizontal bars perpendicular to them.
The $K$ horizontal bars are all at different heights, and the $k$-th horizontal bar from the top connects the $X_k$-th vertical line from the left and the $Y_k$-th vertical line from the left.
The $i$-th number of the sequence follows the $i$-th vertical line from the left of the amidakuji from top to bottom; when it touches a horizontal bar along the way, it moves to the vertical line connected by that bar and continues downward along that vertical line. If it is on the $j$-th vertical line from the left of the amidakuji when it reaches the bottom of the vertical line, that number becomes the $j$-th number of the newly shuffled sequence.

The input is given in the following format.

$N$
$K$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_i$ $Y_i$
$\vdots$
$X_K$ $Y_K$

The first line gives the number of vertical bars $N$.
The second line gives the number of horizontal bars $K$.
The following K lines, starting from the third line, give the vertical lines connected by the $i$-th horizontal bar from the top. The $i$-th horizontal bar from the top connects the $X_i$-th and $Y_i$-th vertical lines counted from the left.

All input values are integers and satisfy the following constraints.
$ 2 \leq N \leq 100 $
$ 0 \leq K \leq 1000 $
$ 1 \leq X_i < Y_i \leq N $
$ X_i + 1 = Y_i $

Output

$S$

Output on one line the minimum number of shuffles $S$ required to return the sequence $1, 2, ... , N$ to the original sequence $1, 2, ... , N$.

Sample

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