← 返回题目列表

AtCoder · abc372_e

H. 第 K 个最大连通分量

中文机器翻译题面 查看原题

分数: 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