문제

In the nearby kindergarten they recently made up an attractive game of strength and agility that kids love. The surface for the game is a large flat area divided into N×N squares. The children lay large spongy cues onto the surface. The sides of the cubes are the same length as the sides of the squares. When a cube is put on the surface, its sides are aligned with some square. A cube may be put on another cube too. Kids enjoy building forts and hiding them, but they always leave behind a huge mess. Because of this, prior to closing the kindergarten, the teachers rearrange all the cubes so that they occupy a rectangle on the surface, with exactly one cube on every square in the rectangle. In one moving, a cube is taken off the top of a square to the top of any other square. Write a program that, given the state of the surface, calculates the smallest number of moves needed to arrange all cubes into a rectangle.

입력

The first line contains the integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ N2), the dimensions of the surface and the number of cubes currently on the surface. Each of the following M lines contains two integers R and C (1 ≤ R, C ≤ N), the coordinates of the square that contains the cube.

출력

Output the smallest number of moves. A solution will always exist.

예제 입력 1

3 2
1 1
1 1

예제 출력 1

1

예제 입력 2

4 3
2 2
4 4
1 1

예제 출력 2

2

예제 입력 3

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

예제 출력 3

3