AT_abc409_f.[ABC409F] Connecting Points

在二维平面上有一个初始为 $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 完成