CHM
Ваше завдання — реалізувати Persistent Disjoint-Set-Union. Що це означає?
Про Disjoint-Set-Union:
Спочатку у вас є n елементів. Потрібно навчитись відповідати на 2 типи запитів.
+ a b — об'єднати множини, у яких лежать вершины a та b;
? a b — сказати, чи лежать вершини a та b зараз в одній множині.
Про Persistent:
Тепер у нас буде декілька копій (версій) структури даних Disjoint-Set-Union.
Запити будуть виглядати так:
+ i a b — запит до i-ї структури, об'єднати множини, до яких належать вершини a та b. При цьомум i-та структура залишається незмінною, створюється нова версія, їй присвоюється новий номер (який? читайте далі);
? i a b — запит до i-ї структури, відповісти, чи лежать вершини a та b зараз в одній множині.
Вхідні дані
У першому рядку 2 числа N (1 ≤ N ≤ 10^5) і K (0 ≤ K ≤ 10^5) — число елементів та число запитів. Спочатку всі елементи знаходяться у різних множинах. Ця початкова копія (версія) структури має номер 0.
Далі йде K рядків, у кожному з яких опис чергового запиту. Формат запитів описано вище. Запити нумеруються цілими числами від 1 до K.
При опрцюванні j-го запиту виду + i a b, нова версія отримає номер j.
Запитів до неіснуючих версій не буде (j > i).
Вихідні дані
Для кожного запиту виду ? i a b у окремому рядку потрібно вивести YES або NO.