Козак Вус та граф
ліміт часу на тест
6 seconds
ліміт використання пам'яті на тест
1024 megabytes
введення
standard input
виведення
standard output

Дано граф з $$$n$$$ вершин. Також дано $$$q$$$ запитів трьох типів:

1. У компоненті вершини $$$v_i$$$ потрібно знайти номер $$$k_i$$$-ої найменшої за номером вершини. Якщо такої немає, то потрібно повернути $$$-1$$$. Компонента вершини $$$v_i$$$ — це множина усіх вершин, до яких можна дістатися з вершини $$$v_i$$$ по ребрах.
2. Додати до графа ребро, що з'єднує вершини $$$u_i$$$ та $$$v_i$$$.
3. Повернутися до стану, який був після виконання $$$x_i$$$ операцій.

Знайдіть відповіді на всі запити першого типу.

Вхідні дані

Перший рядок містить три цілі числа $$$n$$$, $$$q$$$, $$$g$$$ ($$$1 \leq n, q \leq 5 \cdot 10^5$$$, $$$0 \leq g \leq 9$$$).

Кожен з наступних рядків описує запит.

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

Вихідні дані

Для кожного запиту першого типу виведіть відповідь на запит.

Система оцінки

1. ($$$6$$$ балів): $$$n, q \leq 100$$$; немає операцій другого та третього типів.
2. ($$$7$$$ балів): $$$n, q \leq 100$$$; немає операцій третього типу.
3. ($$$4$$$ бали): $$$n, q \leq 100$$$.
4. ($$$9$$$ балів): $$$n, q \leq 3 \cdot 10^5$$$; гарантується, що в операціях другого типу $$$|v_i-u_i|=1$$$; немає запитів третього типу.
5. ($$$8$$$ балів): $$$n, q \leq 3 \cdot 10^5$$$, немає запитів третього типу.
6. ($$$10$$$ балів): $$$n, q \leq 3 \cdot 10^5$$$; гарантується, що в операціях другого типу $$$|v_i-u_i|=1$$$.
7. ($$$19$$$ балів): $$$n, q \leq 10^5$$$.
8. ($$$17$$$ балів): $$$n, q \leq 3 \cdot 10^5$$$.
9. ($$$20$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані

    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