En un círculo infantil donde asisten los niños de los azucareros del centro hicieron recientemente un juego muy atractivo de habilidades que a los niños les gusta. La superficie del juego está en un área de recreo dividida en N*N casillas.
Los niños colocan grandes cubos esponjosos en la superficie. Los lados de los cubos son de la misma longitud que los lados de las casillas. Cuando un cubo se pone en la superficie, sus lados quedan alineados con alguna casilla. Un cubo puede ponerse sobre otro cubo también.
Los chicos disfrutan construyendo fortalezas y escondiéndose en ellas, pero siempre se forma el desorden. Por eso, al cerrar el círculo infantil, los maestros reordenan todos los cubos tal que ellos ocupen un rectángulo en la superficie, con un cubo exactamente en cualquiera de las casillas del perímetro del rectángulo. En un movimiento, se quita un cubo de la parte de arriba de una casilla y se pone en la parte de arriba de cualquier otra casilla.

Escriba un programa que, dado el estado de la superficie, calcule el menor número de movimientos necesarios para ordenar todos los cubos en un rectángulo.

Entrada

La primera línea contiene los enteros N y M (1 ≤ N ≤ 100, 1 ≤ M ≤ N2), las dimensiones de la superficie y el número de cubos actualmente en la superficie. Cada una de las siguientes M líneas contienen dos enteros R y C (1 ≤ R, C ≤ N), las coordenadas del cuadrado que contiene el cubo.

Salida

Imprimir el menor número de movimientos necesarios para ordenar todos los cubos en un rectángulo. Siempre existirá solución.

Ejemplo #1 de Entrada

3 2 
1 1 
1 1

Ejemplo #1 de Salida

1

Ejemplo #2 de Entrada

4 3 
2 2 
4 4 
1 1

Ejemplo #2 de Salida

2

Ejemplo #3 de Entrada

5 8 
2 2 
3 2 
4 2 
2 4 
3 4 
4 4 
2 3 
2 3

Ejemplo #3 de Salida

3