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.