P15049 [UOI 2022 II Stage] Graph 2

Double experience: .

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.

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$).

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

### 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