Background

Double experience: https://www.luogu.com.cn/problem/P5064.

Problem Description

You are given a graph with $n$ vertices. You are also given $q$ queries of three types:

• In the connected component containing vertex $v_i$, find the vertex label that is the $k_i$-th smallest. If it does not exist, output $-1$. The connected component containing $v_i$ means the set of all vertices reachable from $v_i$ by edges.
• Add an edge connecting vertices $u_i$ and $v_i$ to the graph.
• Roll back to the state right after the $x_i$-th operation is executed.

Find the answers to all queries of the first type.

Input Format

The first line contains three integers $n$, $q$, $g$ ($1 \leq n, q \leq 5 \cdot 10^5$, $0 \leq g \leq 9$).

Each of the following lines describes one query:

• Type 1 query: $v_i$, $k_i$ ($1 \leq v_i, k_i \leq n$).
• Type 2 query: $v_i$, $u_i$ ($1 \leq v_i, u_i \leq n$).
• Type 3 query: $x_i$ ($0 \leq x_i < i$).

Output Format

For each type 1 query, output the answer to that query.

10 12 0
1 1 1
2 1 2
2 1 6
2 9 10
2 3 10
2 10 6
1 1 5
1 1 3
3 5
1 1 3
3 0
1 1 3

1
9
3
6
-1

10 17 0
2 1 2
1 2 2
2 3 4
1 3 2
2 6 7
2 7 8
1 7 2
1 7 3
2 5 6
1 5 5
1 5 4
2 5 4
2 3 2
1 1 7
1 1 4
1 1 8
1 1 9

2
4
7
8
-1
8
7
4
8
-1

6 14 0
2 1 6
2 1 3
1 3 2
1 3 3
1 1 1
1 2 1
1 2 6
2 1 2
2 2 2
2 2 1
2 1 5
2 1 4
1 6 6
1 1 5

3
6
1
2
-1
6
5

5 5 0
2 1 2
1 1 2
3 0
2 1 3
1 1 2

2
3

Hint

Scoring

• (6 points): $n, q \leq 100$; there are no type 2 or type 3 operations.
• (7 points): $n, q \leq 100$; there are no type 3 operations.
• (4 points): $n, q \leq 100$.
• (9 points): $n, q \leq 3 \cdot 10^5$; it is guaranteed that in type 2 operations $|v_i - u_i| = 1$; there are no type 3 queries.
• (8 points): $n, q \leq 3 \cdot 10^5$; there are no type 3 queries.
• (10 points): $n, q \leq 3 \cdot 10^5$; it is guaranteed that in type 2 operations $|v_i - u_i| = 1$.
• (19 points): $n, q \leq 10^5$.
• (17 points): $n, q \leq 3 \cdot 10^5$.
• (20 points): No additional constraints.

Translated by DeepSeek V3.

Translated by ChatGPT 5