돌멩이 제거

n행 n열 격자로 나뉜 운동장에 k개의 돌멩이가 놓여 있다. 돌멩이 하나는 정확히 한 칸에 들어 있으며, 같은 칸에 두 개 이상의 돌멩이가 놓이는 경우는 없다.

돌멩이를 치우려면 한 번에 한 행 또는 한 열을 골라 그 직선을 따라 달리며 그 위에 있는 모든 돌멩이를 줍는다.

운동장의 상태가 주어질 때, 모든 돌멩이를 줍기 위해 필요한 달리기 횟수의 최솟값을 구하라.

첫째 줄에 정수 n과 k가 주어진다. (1 <= n <= 500, 1 <= k <= 10,000)

다음 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 각 줄의 첫 번째 정수는 행 번호, 두 번째 정수는 열 번호이다. 입력으로 주어지는 위치는 서로 모두 다르다.

모든 돌멩이를 줍는 데 필요한 최소 달리기 횟수를 출력한다.

돌멩이가 있는 칸을 X, 없는 칸을 _로 나타내면 다음과 같은 배치가 될 수 있다.

X _ X_ X __ X _

1행을 따라 달리면 (1, 1), (1, 3)의 돌멩이를 주울 수 있다. 이어서 2열을 따라 달리면 (2, 2), (3, 2)의 돌멩이를 주울 수 있으므로 두 번의 달리기로 모든 돌멩이를 제거할 수 있다.