分数: 500 点
问题陈述
有一张图 G 与 N 顶点和 0 边缘 2维度平面。顶点编号从 1 to N,和顶点 i 位于坐标处 (x_i,y_i).
对于顶点 u 和 v of G,距离 d(u,v) 之间 u 和 v 定义为曼哈顿距离 d(u,v)=|x_u-x_v|+|y_u-y_v|.
另外,对于两个连接的组件 A 和 B of G,让 V(A) 和 V(B) 是顶点集 分别为 A 和 B。距离 d(A,B) 之间 A 和 B 定义为 d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace.
流程 Q 查询如下所述。每个查询都是以下三种类型之一:
1 a b:让 n 是顶点数 G。添加顶点 n+1 to G 坐标 (x_{n+1},y_{n+1})=(a,b).2:让 n 是顶点数 G 和 m 是连接组件的数量。- If m=1,输出
-1. - If m\geq 2,合并所有具有最小距离的连通分量并输出该最小距离的值。形式上,让连通分量 G be A_1,A_2,\ldots,A_m 并让 \displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j)。对于所有顶点对 (u,v)\ (1\leq u\lt v\leq n) 不在同一连接组件中并且满足 d(u,v)=k,在顶点之间添加一条边 u 和 v。然后,输出 k.
- If m=1,输出
3 u v:如果顶点 u 和 v 位于同一连接组件中,输出Yes;否则,输出No.
约束
- 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,让 n 是顶点数 G 在处理该查询之前,然后 1\leq u\lt v\leq n.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{query}_i 是 i要处理的第一个查询。
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
输出
按照问题陈述中的说明输出由换行符分隔的查询的答案。
示例输入 1
4 11 3 4 3 3 7 3 2 2 3 1 2 2 3 1 2 1 6 4 2 3 2 5 2 3 2 5 2 1 2 2 2
示例输出 1
No 1 Yes 2 No 3 Yes -1 0
最初,顶点 1,2,3,4 位于坐标处 (3,4),(3,3),(7,3),(2,2)。
- 对于 1st 查询,顶点 1 和 2 未连接,因此输出
No. - 对于 2nd查询,有 4 连通分量,每个连通分量的顶点集是 \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace。不同连通分量之间的最小距离为 1,并在顶点之间添加一条边 1 和 2。输出 1.
- 对于 3rd 查询,顶点 1 和 2 已连接,因此输出
Yes. - 对于 4第查询,添加顶点 5 位于坐标处 (6,4).
- 对于 5第次查询,有 4 连通分量,每个连通分量的顶点集是 \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace。不同连通分量之间的最小距离为 2,并且在顶点之间添加边 2 和 4 和顶点之间 3 和 5。输出 2.
- 对于 6th 查询,顶点 2 和 5 未连接,因此输出
No. - 对于 7第次查询,有 2 连通分量,每个连通分量的顶点集是 \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace。不同连通分量之间的最小距离为 3,并在顶点之间添加一条边 1 和 5。输出 3.
- 对于 8th 查询,顶点 2 和 5 已连接,因此输出
Yes. - 对于 9第查询,有 1 连接组件,因此输出 -1.
- 对于 10第查询,添加顶点 6 位于坐标处 (2,2).
- 对于 11第次查询,有 2 连通分量,每个连通分量的顶点集是 \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace。不同连通分量之间的最小距离为 0,并在顶点之间添加一条边 4 和 6。输出 0.