U610927 老逗找基友

吴老逗有 $n$ 个基友，位于平面直角坐标系的整点上。每个基友已与其最近的基友（如有多个则取编号最小）建立了双向心灵感应。但这样形成的网络可能不连通，因此吴老逗可以使用爱之魔法（连接自己与某个基友）来使网络连通。目标是使用最少的魔法次数使网络连通，并最小化连通网络中任意两个基友之间的最大距离（这里距离指感应次数，即边数）。

给定 $n$ 个点 $(x_i, y_i)$，点 $i$ 与点 $j$ 的距离定义为曼哈顿距离 $|x_i - x_j| + |y_i - y_j|$。初始时，每个点都连接其最近点（多个最近点时取编号最小）。这样得到一个图（可能不连通）。现在可以添加若干条边（每条边连接吴老逗（编号0）和某个基友），要求添加最少的边使图连通，并求连通后图的直径（即任意两点间最短路径的最大值）的最小可能值。

- 第一行：正整数 $n$。 - 接下来 $n$ 行：每行两个整数 $x, y$。

- 一行：一个正整数，表示两个基友相隔感应次数的最小值的最大值（即最小可能直径）。

### 数据规模 - 对于 $30$% 的数据，$n \leq 2×10^3$。 - 对于另外 $30$% 的数据，$n \leq 10^5$，$0 \leq x,y \leq 10^3$。 - 对于 $100$% 的数据，$n \leq 10^5$，$x,y \leq 10^9$。