Дано граф з n вершин. Також дано q запитів трьох типів:
У компоненті вершини vi потрібно знайти номер ki-ої найменшої за номером вершини. Якщо такої немає, то потрібно повернути −1. Компонента вершини vi — це множина усіх вершин, до яких можна дістатися з вершини vi по ребрах.
Додати до графа ребро, що з'єднує вершини ui та vi.
Повернутися до стану, який був після виконання xi операцій.
Знайдіть відповіді на всі запити першого типу.
Перший рядок містить три цілі числа n, q, g (1≤n,q≤5⋅105, 0≤g≤9).
Кожен з наступних рядків описує запит.
vi, ki (1≤vi,ki≤n).
vi, ui (1≤vi,ui≤n).
xi (0≤xi<i).
Для кожного запиту першого типу виведіть відповідь на запит.
(6 балів): n,q≤100; немає операцій другого та третього типів.
(7 балів): n,q≤100; немає операцій третього типу.
(4 бали): n,q≤100.
(9 балів): n,q≤3⋅105; гарантується, що в операціях другого типу ∣vi−ui∣=1; немає запитів третього типу.
(8 балів): n,q≤3⋅105, немає запитів третього типу.
(10 балів): n,q≤3⋅105; гарантується, що в операціях другого типу ∣vi−ui∣=1.
(19 балів): n,q≤105.
(17 балів): n,q≤3⋅105.
(20 балів): без додаткових обмежень.