eolymp
bolt
Try our new interface for solving problems

CHM

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Ваша задача — реализовать 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 сейчас в одном множестве.

Giriş verilənləri

На первой строке 2 числа N (1N10^5) и K (0K10^5) — число элементов и число запросов. Изначально все элементы находятся в различных множествах. Эта изначальная копия (версия) структуры имеет номер 0.

Далее следуют K строк, на каждой описание очередного запроса. Формат запросов описан выше. Запросы нумеруются целыми числами от 1 до K.

При обработке j-го запроса вида + i a b, новая версия получит номер j.

Запросов к несуществующим версиям не будет (j > i).

Çıxış verilənləri

Для каждого запроса вида ? i a b на отдельной строке нужно вывести YES или NO.

Nümunə

Giriş verilənləri #1
4 7
+ 0 1 2
? 0 1 2
? 1 1 2
+ 1 2 3
? 4 3 1
? 0 4 4
? 4 1 4
Çıxış verilənləri #1
NO
YES
YES
YES
NO
Müəllif Сергей Копелиович
Mənbə Зимняя школа, Харьков 2011, День 5