[문제요약] 아이들이 좋아하는 게임을 최근 준비 했다.

게임판은 N×N 크기이다.

아이들은 표면에 큰 스펀지 정육면제를 놓는다. 정육면체의 면은 같은 크기이다 판의 정사각형과 같은 크기이다. 큐브를 놓을 때 면은 셀과 나란히 두고 정육면체 위에 정육면체가 올라 갈 수 있다.

아이들은 요새를 짓거나 감추는 것을 좋아하지만 나중에 난장판이 되어 버린다. 이 것 때문에 , 유치원에 마치기전에 , 선생님들은 모든 큐브를 면에 직육면체로 정리를 하려고 한다. 직사각형의 한 셀에 하나의 정육면체가 놓이도록.

한 번 이동에 한 큐브위에 있는 큐브가 이동이 가능하다.

판의 상태가 주어질 때 가장 최소 이동으로 높이가 1 인 직육면체를 만드는 것이 문제이다.

첫 번째 예시에는 1,1 에 놓여 있는 두 개중 위에 있는 것을 1,2 혹은 2,1 로 옮기면 가능하고 세 번째 예시에서는 (2, 3) to (3, 3), from (4, 2) to (2, 5) and from (4, 4) to (3, 5) 로 옮기면 아래 그림과 같은 직육면체를 만들 수 있다.

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 ≤ N^ 2), 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.

출력

입출력 예

입력

3 2 
1 1 
1 1 

출력 

1 

입력 

4 3 
2 2 
4 4 
1 1 

출력 

2 

입력 

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

출력 

3 

EXAMPLES

출처: coci 2008/2009 contest6 3/6