103724: [Atcoder]ABC372 E - K-th Largest Connected Components

Problem Statement

There is an undirected graph with $N$ vertices and $0$ edges. The vertices are numbered $1$ to $N$.

You are given $Q$ queries to process in order. Each query is of one of the following two types:

• Type $1$: Given in the format 1 u v. Add an edge between vertices $u$ and $v$.
• Type $2$: Given in the format 2 v k. Print the $k$-th largest vertex number among the vertices connected to vertex $v$. If there are fewer than $k$ vertices connected to $v$, print -1.

Constraints

• $1 \leq N, Q \leq 2 \times 10^5$
• In a Type $1$ query, $1 \leq u < v \leq N$.
• In a Type $2$ query, $1 \leq v \leq N$, $1 \leq k \leq 10$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

Here, $\mathrm{query}_i$ is the $i$-th query and is given in one of the following formats:

$1$ $u$ $v$

$2$ $v$ $k$

Output

Let $q$ be the number of Type $2$ queries. Print $q$ lines. The $i$-th line should contain the answer to the $i$-th Type $2$ query.

Sample Input 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

Sample Output 1

2
1
-1
4
2
-1

• In the first query, an edge is added between vertices $1$ and $2$.
• In the second query, two vertices are connected to vertex $1$: $1$ and $2$. Among them, the $1$-st largest vertex number is $2$, which should be printed.
• In the third query, two vertices are connected to vertex $1$: $1$ and $2$. Among them, the $2$-nd largest vertex number is $1$, which should be printed.
• In the fourth query, two vertices are connected to vertex $1$: $1$ and $2$, which is fewer than $3$, so print -1.
• In the fifth query, an edge is added between vertices $1$ and $3$.
• In the sixth query, an edge is added between vertices $2$ and $3$.
• In the seventh query, an edge is added between vertices $3$ and $4$.
• In the eighth query, four vertices are connected to vertex $1$: $1,2,3,4$. Among them, the $1$-st largest vertex number is $4$, which should be printed.
• In the eighth query, four vertices are connected to vertex $1$: $1,2,3,4$. Among them, the $3$-rd largest vertex number is $2$, which should be printed.
• In the tenth query, four vertices are connected to vertex $1$: $1,2,3,4$, which is fewer than $5$, so print -1.

Sample Input 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

Sample Output 2

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

问题陈述

有一个有N个顶点和0条边的无向图。顶点编号为1到N。

你需要按顺序处理Q个查询。每个查询都是以下两种类型之一：

• 类型1：格式为1 u v。在顶点u和v之间添加一条边。
• 类型2：格式为2 v k。打印与顶点v相连的顶点中第k大的顶点编号。如果与v相连的顶点少于k个，打印-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个查询，并且以以下格式之一给出：

$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大的顶点编号是2，应该被打印。
• 在第三个查询中，与顶点1相连的两个顶点是：1和2。其中，第2大的顶点编号是1，应该被打印。
• 在第四个查询中，与顶点1相连的两个顶点是：1和2，少于3个，所以打印-1。
• 在第五个查询中，在顶点1和3之间添加了一条边。
• 在第六个查询中，在顶点2和3之间添加了一条边。
• 在第七个查询中，在顶点3和4之间添加了一条边。
• 在第八个查询中，与顶点1相连的四个顶点是：1,2,3,4。其中，第1大的顶点编号是4，应该被打印。
• 在第九个查询中，与顶点1相连的四个顶点是：1,2,3,4。其中，第3大的顶点编号是2，应该被打印。
• 在第十个查询中，与顶点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