Задачи
Система непересекающихся множеств
Система непересекающихся множеств
Реализуйте систему непересекающихся множеств. На структуре данных нужно выполнить набор запросов двух типов:
union u v - объединить два множества, содержащие u и v соответственно;
get u v - проверить лежат ли элементы u и v в одном множестве.
Входные данные
Первая строка содержит два числа n и m (1 ≤ n, m ≤ 5 * 10^5
) - число элементов и число запросов. Далее идут m строк запросов, по одному на строке.
Для запросов union строка выглядит как union u v (1 ≤ u, v ≤ n).
Для запросов get строка выглядит как get u v (1 ≤ u, v ≤ n).
Выходные данные
Выведите результат каждой операции get по одной на строке в соответствующем порядке: "YES", если элементы лежат в одном множестве, и "NO", в противном случае.
Пример
Входные данные #1
4 4 union 1 2 union 1 3 get 1 4 get 2 3
Выходные данные #1
NO YES