分数: 475 点
问题陈述
有一个无向图 N 顶点和 0 边缘。顶点已编号 1 to N.
你被给予 Q 查询按顺序处理。每个查询属于以下两种类型之一:
- 类型 1:以格式给出
1 u v。在顶点之间添加边 u 和 v. - 类型 2:以格式给出
2 v k。打印 k- 与顶点相连的顶点中第最大的顶点编号 v。如果少于 k 顶点连接到 v,打印-1.
约束
- 1 \leq N, Q \leq 2 \times 10^5
- 在类型中 1 查询, 1 \leq u < v \leq N.
- 在类型中 2 查询, 1 \leq v \leq N, 1 \leq k \leq 10.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_i 是 i-th 查询并以下列格式之一给出:
1 u v
2 v k
输出
让 q 是类型的数量 2 查询。打印 q 行。 的 i- 第行应包含以下问题的答案 i-第类型 2 查询。
示例输入 1
4 10 1 1 2 2 1 1 2 1 2 2 1 3 1 1 3 1 2 3 1 3 4 2 1 1 2 1 3 2 1 5
示例输出 1
2 1 -1 4 2 -1
- 在第一个查询中,在顶点之间添加一条边 1 和 2.
- 在第二个查询中,两个顶点连接到顶点 1: 1 和 2。其中, 1-st 最大顶点数是 2,应打印。
- 在第三个查询中,两个顶点连接到顶点 1: 1 和 2。其中, 2-nd 最大顶点数是 1,应打印。
- 在第四个查询中,两个顶点连接到顶点 1: 1 和 2,小于 3,所以打印
-1. - 在第五个查询中,顶点之间添加了一条边 1 和 3.
- 在第六个查询中,在顶点之间添加一条边 2 和 3.
- 在第七个查询中,在顶点之间添加一条边 3 和 4.
- 在第八个查询中,四个顶点连接到vertex 1: 1,2,3,4。其中, 1-st 最大顶点数是 4,应打印。
- 在第九个查询中,四个顶点连接到vertex 1: 1,2,3,4。其中, 3-rd 最大顶点数是 2,应打印。
- 第十个查询中,四个顶点连接到vertex 1: 1,2,3,4,小于 5,所以打印
-1.
示例输入 2
6 20 1 3 4 1 3 5 2 1 1 2 3 1 1 1 5 2 6 9 2 1 3 2 6 1 1 4 6 2 2 1 2 6 2 2 4 7 1 1 4 2 6 2 2 3 4 1 2 5 2 4 1 1 1 6 2 3 3 2 1 3
示例输出 2
1 5 -1 3 6 2 5 -1 5 3 6 4 4