Farmer John quer conectar $N$ celeiros ($1 \le N \le 1{,}000$), numerados $1..N$, por fibra óptica. Circundam um lago em círculo, logo só se conectam vizinhos; o celeiro $N$ é vizinho do 1.

Não precisa conectar todos: só certos pares de vacas querem comunicar. Quer o mínimo de conexões que permita todas essas comunicações pela rede. Dados os pares, ache o mínimo de linhas. Para comunicar 1 com 3, devem ser colocadas 1-2 e 2-3.

Entrada

• Linha $1$: inteiros $N$ e $P$, este último é o número de pares ($1 \le P \le 10{,}000$).

• Linhas $2..P+1$: dois inteiros que indicam um par de celeiros que deseja comunicar. Não há pares repetidos.

Saída

Uma linha com um inteiro, o mínimo de conexões diretas necessárias.

Exemplos

Entrada 1

5 2
1 3
4 5

Saída 1

3

Note

Conectam os pares 1-2, 2-3 e 4-5.

Créditos: Reid Barton, 2001.