문명

문명은 홀로 발전하기도 하고, 서로 다른 문명이 만나 하나로 합쳐지기도 한다. 이 가설을 바탕으로 세계 문명의 발전 과정을 시뮬레이션한다.

세계는 $N \times N$ 크기의 2차원 공간이다. 한 변의 길이가 1인 정사각형이 가로와 세로로 $N$개씩 놓여 있고, 가장 왼쪽 아래 정사각형의 위치는 $(1, 1)$, 가장 오른쪽 위 정사각형의 위치는 $(N, N)$이다. 두 정사각형 $(a, b)$와 $(a', b')$은 다음 두 조건 중 하나를 만족할 때 서로 인접하다.

• $|a - a'| = 1$이고 $b = b'$이다.
• $|b - b'| = 1$이고 $a = a'$이다.

문명의 최초 발상지는 서로 다른 $K$곳이다. 각 정사각형은 문명 지역이거나 미개 지역이고, 발상지는 모두 문명 지역이다. 발상지끼리 인접해 있으면 처음부터 하나로 결합된다. 한 해가 지날 때마다 문명 지역은 인접한 지역으로 문명을 전파한다. 즉 정사각형 $(a, b)$가 문명 지역이면 다음 해에는 세계의 경계를 벗어나지 않는 $(a+1, b)$, $(a-1, b)$, $(a, b+1)$, $(a, b-1)$이 모두 문명 지역이 된다. 인접한 두 지역에 서로 다른 문명이 전파되었거나 한 지역에 둘 이상의 문명이 전파되면 그 문명들은 결합된다. 결합은 간접적으로도 이어진다. 문명 A와 문명 B가 결합하고 문명 B와 문명 C가 결합하면 A와 C도 하나의 문명이다.

위 그림은 $N = 5$이고 발상지가 $(1, 1)$, $(2, 1)$, $(2, 5)$, $(5, 2)$인 경우다. $(1, 1)$과 $(2, 1)$은 인접하므로 처음부터 결합되어 있다. 왼쪽은 1년 뒤, 오른쪽은 2년 뒤의 문명 지역이며, 2년이 지나면 네 발상지의 문명이 모두 하나가 된다. $(2, 5)$의 문명과 $(5, 2)$의 문명은 직접 맞닿지 않았지만 $(1, 1)$과 $(2, 1)$의 문명을 거쳐 결합된다.

세계의 크기와 발상지의 수 및 위치가 주어질 때, 모든 문명이 하나로 결합되기까지 걸리는 최소 햇수를 구하는 프로그램을 작성하시오.

첫 줄에 세계의 크기 $N$($2 \le N \le 2000$)과 문명 발상지의 수 $K$($2 \le K \le 100000$)가 주어진다. 다음 $K$개의 줄에는 발상지에 해당하는 정사각형의 위치 $x$와 $y$가 한 줄에 하나씩 주어진다($1 \le x, y \le N$). 발상지 $K$곳의 위치는 모두 다르다.

모든 문명이 하나로 결합되기까지 걸리는 최소 햇수를 정수 하나로 출력한다.