Cossack Vus and the Count

Çox çətin

Zaman limiti 6 saniyə-dir

Yaddaş məhdudiyyəti 1.024 meqabayt

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

For a given vertex $v_{i}$ , find the $k_{i}$ -th smallest vertex number in its connected component. If such a vertex does not exist, return $- 1$ . The connected component of $v_{i}$ includes all vertices reachable from $v_{i}$ via edges.
Add an edge between vertices $u_{i}$ and $v_{i}$ .
Revert the graph to its state after the $x_{i}$ -th operation.

Your task is to provide answers for all queries of the first type.

Giriş verilənləri

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

Each of the following lines contains a query in one of the following formats:

For each query of the first type, output the result.

Giriş #1

Çıxış #1

Giriş #2

Çıxış #2

Giriş #3

Çıxış #3

Giriş #4

Çıxış #4

( $6$ points): $n, q \leq 100$ ; no queries of the second and third types.
( $7$ points): $n, q \leq 100$ ; no queries of the third type.
( $4$ points): $n, q \leq 100$ .
( $9$ points): $n, q \leq 3 \cdot 1 0^{5}$ ; for queries of the second type, it is guaranteed that $∣ v_{i} - u_{i} ∣ = 1$ ; no queries of the third type.
( $8$ points): $n, q \leq 3 \cdot 1 0^{5}$ , no queries of the third type.
( $10$ points): $n, q \leq 3 \cdot 1 0^{5}$ ; for queries of the second type, it is guaranteed that $∣ v_{i} - u_{i} ∣ = 1$ .
( $19$ points): $n, q \leq 1 0^{5}$ .
( $17$ points): $n, q \leq 3 \cdot 1 0^{5}$ .
( $20$ points): no additional constraints.

Təqdimatlar 17

Qəbul dərəcəsi 18%