连通分量的第 K 大顶点

题目描述

有一个具有 $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 查询的答案。

样例

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

2
1
-1
4
2
-1

第一个查询在顶点 $1$ 和 $2$ 之间添加了一条边。

第二个查询中，与顶点 $1$ 相连通的顶点是 $1$ 和 $2$，共两个。其中第 $1$ 大的顶点编号是 $2$，应输出 $2$。

第三个查询中，与顶点 $1$ 相连通的顶点是 $1$ 和 $2$，共两个。其中第 $2$ 大的顶点编号是 $1$，应输出 $1$。

第四个查询中，与顶点 $1$ 相连通的顶点是 $1$ 和 $2$，少于 $3$ 个，所以输出 -1。

第五个查询在顶点 $1$ 和 $3$ 之间添加了一条边。

第六个查询在顶点 $2$ 和 $3$ 之间添加了一条边。

第七个查询在顶点 $3$ 和 $4$ 之间添加了一条边。

第八个查询中，与顶点 $1$ 相连通的顶点是 $1,2,3,4$，共四个。其中第 $1$ 大的顶点编号是 $4$，应输出 $4$。

第九个查询中，与顶点 $1$ 相连通的顶点是 $1,2,3,4$，共四个。其中第 $3$ 大的顶点编号是 $2$，应输出 $2$。

第十个查询中，与顶点 $1$ 相连通的顶点是 $1,2,3,4$，少于 $5$ 个，所以输出 -1。

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

1
5
-1
3
6
2
5
-1
5
3
6
4
4

数据范围

• $1 \leq N, Q \leq 2 \times 10^5$
• 类型 1 查询中，$1 \leq u \lt v \leq N$
• 类型 2 查询中，$1 \leq v \leq N$，$1 \leq k \leq 10$
• 输入中的所有数值均为整数