Дано граф з вершин. Також дано запитів трьох типів:
У компоненті вершини v_i потрібно знайти номер k_i-ої найменшої за номером вершини. Якщо такої немає, то потрібно повернути . Компонента вершини v_i — це множина усіх вершин, до яких можна дістатися з вершини v_i по ребрах.
Додати до графа ребро, що з'єднує вершини u_i та v_i.
Повернутися до стану, який був після виконання x_i операцій.
Знайдіть відповіді на всі запити першого типу.
Перший рядок містить три цілі числа , , (1 \leq n, q \leq 5 \cdot 10^5, 0 \leq g \leq 9).
Кожен з наступних рядків описує запит.
v_i, k_i (1 \leq v_i, k_i \leq n).
v_i, u_i (1 \leq v_i, u_i \leq n).
x_i (0 \leq x_i < i).
Для кожного запиту першого типу виведіть відповідь на запит.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
( балів): n, q \leq 100; немає операцій другого та третього типів.
( балів): n, q \leq 100; немає операцій третього типу.
( балів): n, q \leq 100.
( балів): n, q \leq 3 \cdot 10^5; гарантується, що в операціях другого типу |v_i-u_i|=1; немає запитів третього типу.
( балів): n, q \leq 3 \cdot 10^5, немає запитів третього типу.
( балів): n, q \leq 3 \cdot 10^5; гарантується, що в операціях другого типу |v_i-u_i|=1.
( балів): n, q \leq 10^5.
( балів): n, q \leq 3 \cdot 10^5.
( балів): без додаткових обмежень.