Farmer John quiere conectar $N$ graneros ($1 \le N \le 1{,}000$), numerados $1..N$, con fibra óptica. Rodean un estanque en círculo, así que solo se pueden conectar vecinos; el granero $N$ es vecino del 1.

No necesita conectar todos: solo ciertas parejas de vacas desean comunicarse. Quiere el mínimo de conexiones que permita todas esas comunicaciones por la red. Dadas las parejas, halla el mínimo de líneas. Para comunicar 1 con 3, deben tenderse 1-2 y 2-3.

Entrada

• Línea $1$: enteros $N$ y $P$, este último es el número de parejas ($1 \le P \le 10{,}000$).

• Líneas $2..P+1$: dos enteros que indican una pareja de graneros que desea comunicarse. No hay parejas repetidas.

Salida

Una línea con un entero, el mínimo de conexiones directas necesarias.

Ejemplos

Entrada 1

5 2
1 3
4 5

Salida 1

3

Nota

Conectan las parejas 1-2, 2-3 y 4-5.

Créditos: Reid Barton, 2001.