Козак Вус та граф#101

Козак Вус та граф

6 секунд
1 024 мегабайти
Дуже складна

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

  1. У компоненті вершини v_i потрібно знайти номер k_i-ої найменшої за номером вершини. Якщо такої немає, то потрібно повернути . Компонента вершини v_i — це множина усіх вершин, до яких можна дістатися з вершини v_i по ребрах.

  2. Додати до графа ребро, що з'єднує вершини u_i та v_i.

  3. Повернутися до стану, який був після виконання x_i операцій.

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

Вхідні дані

Перший рядок містить три цілі числа , , (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

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Приклад 4

Loading
Loading

Оцінювання

  1. ( балів): n, q \leq 100; немає операцій другого та третього типів.

  2. ( балів): n, q \leq 100; немає операцій третього типу.

  3. ( балів): n, q \leq 100.

  4. ( балів): n, q \leq 3 \cdot 10^5; гарантується, що в операціях другого типу |v_i-u_i|=1; немає запитів третього типу.

  5. ( балів): n, q \leq 3 \cdot 10^5, немає запитів третього типу.

  6. ( балів): n, q \leq 3 \cdot 10^5; гарантується, що в операціях другого типу |v_i-u_i|=1.

  7. ( балів): n, q \leq 10^5.

  8. ( балів): n, q \leq 3 \cdot 10^5.

  9. ( балів): без додаткових обмежень.