AT_abc409_f [ABC409F] Connecting Points

[problemUrl]: https://atcoder.jp/contests/abc409/tasks/abc409_f 在二维平面上有一个初始为 $N$ 个顶点、$0$ 条边的图 $G$。顶点编号为 $1$ 到 $N$，顶点 $i$ 的坐标为 $(x_i,y_i)$。 对于图 $G$ 中的顶点 $u$ 和 $v$，定义它们之间的距离 $d(u,v)$ 为曼哈顿距离：$d(u,v)=|x_u-x_v|+|y_u-y_v|$。 对于图 $G$ 的两个连通分量 $A$ 和 $B$，设它们的顶点集合分别为 $V(A)$ 和 $V(B)$，则定义 $A$ 和 $B$ 之间的距离 $d(A,B)$ 为：$d(A,B)=\min\lbrace d(u,v) \mid u \in V(A), v \in V(B) \rbrace$。 请处理以下 $Q$ 个查询，查询分为三种类型： 1. `1 a b`：设当前图 $G$ 的顶点数为 $n$，在坐标 $(a,b)$ 处新增顶点 $n+1$，并将其加入图 $G$。 2. `2`：设当前图 $G$ 的顶点数为 $n$，连通分量数为 $m$： - 若 $m=1$，输出 `-1`。 - 若 $m \geq 2$，找到距离最小的连通分量对，并将它们合并（即在这些连通分量之间添加边，使得所有距离等于最小值的顶点对相连），然后输出该最小距离值。 3. `3 u v`：若顶点 $u$ 和 $v$ 属于同一连通分量，输出 `Yes`；否则输出 `No`。

输入通过标准输入给出，格式如下： > $N$ $Q$ > $x_1$ $y_1$ > $x_2$ $y_2$ > $\vdots$ > $x_N$ $y_N$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个查询为以下三种形式之一： > $1$ $a$ $b$ > $2$ > $3$ $u$ $v$

按照题目要求输出每个查询的结果，每个结果占一行。

### 约束条件 - $2 \leq N \leq 1500$ - $1 \leq Q \leq 1500$ - $0 \leq x_i, y_i \leq 10^9$ - 对于类型 `1` 的查询，$0 \leq a, b \leq 10^9$ - 对于类型 `3` 的查询，设处理该查询前图 $G$ 的顶点数为 $n$，则 $1 \leq u < v \leq n$ - 输入均为整数 ### 样例解释 1 初始时，顶点 $1,2,3,4$ 的坐标分别为 $(3,4),(3,3),(7,3),(2,2)$。 - 第 1 个查询：顶点 $1$ 和 $2$ 不连通，输出 `No`。 - 第 2 个查询：有 4 个连通分量（$\lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace$），最小距离为 $1$（顶点 $1$ 和 $2$ 之间），合并后输出 $1$。 - 第 3 个查询：顶点 $1$ 和 $2$ 已连通，输出 `Yes`。 - 第 4 个查询：新增顶点 $5$，坐标为 $(6,4)$。 - 第 5 个查询：最小距离为 $2$（顶点 $2$ 和 $4$、顶点 $3$ 和 $5$ 之间），合并后输出 $2$。 - 第 6 个查询：顶点 $2$ 和 $5$ 不连通，输出 `No`。 - 第 7 个查询：最小距离为 $3$（顶点 $1$ 和 $5$ 之间），合并后输出 $3$。 - 第 8 个查询：顶点 $2$ 和 $5$ 已连通，输出 `Yes`。 - 第 9 个查询：所有顶点连通，输出 `-1`。 - 第 10 个查询：新增顶点 $6$，坐标为 $(2,2)$。 - 第 11 个查询：最小距离为 $0$（顶点 $4$ 和 $6$ 之间），合并后输出 $0$。 翻译由 DeepSeek V3 完成