AT_abc372_e [ABC372E] K-th Largest Connected Components

有一个包含 $N$ 个顶点、$0$ 条边的无向图。顶点编号为 $1$ 到 $N$。 给定 $Q$ 个查询，请按给定顺序依次处理。每个查询有以下两种类型之一： - 类型 $1$：以 `1 u v` 的形式给出。在顶点 $u$ 和顶点 $v$ 之间添加一条边。 - 类型 $2$：以 `2 v k` 的形式给出。在与顶点 $v$ 连通的所有顶点中，输出编号第 $k$ 大的顶点编号。如果与顶点 $v$ 连通的顶点不足 $k$ 个，则输出 `-1`。

输入以如下格式从标准输入读入。 > $N$ $Q$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 其中，$\mathrm{query}_i$ 表示第 $i$ 个查询，格式如下之一： > $1$ $u$ $v$ > $2$ $v$ $k$

设类型 $2$ 的查询有 $q$ 个，请输出 $q$ 行。第 $i$ 行输出第 $i$ 个类型 $2$ 查询的答案。

### 数据范围 - $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$ - 所有输入均为整数 ### 样例解释 1 - 第 $1$ 个查询，在顶点 $1$ 和顶点 $2$ 之间添加一条边。 - 第 $2$ 个查询，与顶点 $1$ 连通的顶点有 $1,2$ 共 $2$ 个。在这些顶点中，第 $1$ 大的是 $2$，输出 $2$。 - 第 $3$ 个查询，与顶点 $1$ 连通的顶点有 $1,2$ 共 $2$ 个。在这些顶点中，第 $2$ 大的是 $1$，输出 $1$。 - 第 $4$ 个查询，与顶点 $1$ 连通的顶点有 $1,2$ 共 $2$ 个，不足 $3$ 个，输出 `-1`。 - 第 $5$ 个查询，在顶点 $1$ 和顶点 $3$ 之间添加一条边。 - 第 $6$ 个查询，在顶点 $2$ 和顶点 $3$ 之间添加一条边。 - 第 $7$ 个查询，在顶点 $3$ 和顶点 $4$ 之间添加一条边。 - 第 $8$ 个查询，与顶点 $1$ 连通的顶点有 $1,2,3,4$ 共 $4$ 个。在这些顶点中，第 $1$ 大的是 $4$，输出 $4$。 - 第 $9$ 个查询，与顶点 $1$ 连通的顶点有 $1,2,3,4$ 共 $4$ 个。在这些顶点中，第 $3$ 大的是 $2$，输出 $2$。 - 第 $10$ 个查询，与顶点 $1$ 连通的顶点有 $1,2,3,4$ 共 $4$ 个，不足 $5$ 个，输出 `-1`。 由 ChatGPT 4.1 翻译