Civilization

A civilization can grow on its own, and two different civilizations can meet and merge into one. Starting from that assumption, you simulate how the civilizations of a world develop.

The world is a two-dimensional space of size $N \times N$. It holds $N$ unit squares along each side. The bottom left square is at position $(1, 1)$ and the top right square is at position $(N, N)$. Two squares $(a, b)$ and $(a', b')$ are adjacent when exactly one of the following holds.

• $|a - a'| = 1$ and $b = b'$.
• $|b - b'| = 1$ and $a = a'$.

Civilizations start at $K$ distinct squares. Every square is either civilized or wild, and every starting square is civilized. If two starting squares are adjacent, their civilizations are merged from the beginning. Each year every civilized square spreads its civilization to the squares next to it. If square $(a, b)$ is civilized, then one year later $(a+1, b)$, $(a-1, b)$, $(a, b+1)$ and $(a, b-1)$ are all civilized, as long as they stay inside the world. When two adjacent squares hold different civilizations, or when more than one civilization reaches the same square, those civilizations merge. Merging is transitive: if A merges with B and B merges with C, then A and C are the same civilization.

The picture shows the case $N = 5$ with starting squares $(1, 1)$, $(2, 1)$, $(2, 5)$ and $(5, 2)$. The squares $(1, 1)$ and $(2, 1)$ are adjacent, so their civilizations are merged from the start. The left side is the civilized area after one year and the right side is the area after two years. After two years all four civilizations form a single one. The civilization from $(2, 5)$ and the one from $(5, 2)$ never touch each other directly; they merge through the civilization of $(1, 1)$ and $(2, 1)$.

Given the size of the world and the number and positions of the starting squares, write a program that computes the smallest number of years needed until all civilizations become one.

The first line contains the size of the world $N$ ($2 \le N \le 2000$) and the number of starting squares $K$ ($2 \le K \le 100000$). Each of the next $K$ lines contains two integers $x$ and $y$, the position of one starting square ($1 \le x, y \le N$). The $K$ starting positions are all different.

Print a single integer, the smallest number of years until all civilizations merge into one.