Почти Union-Find
Почти Union-Find
Надеюсь, Вы знаете красивую структуру Union-Find. В этой задаче Вам следует реализовать нечто похожее, но не идентичное.
Структура данных, которую Вы должны написать, представляет собой набор непересекающихся множеств, поддерживающих 3 операции:
1 p q Объединить множества, содержащие p и q. Если p и q уже в одном и том же множестве, игнорируйте эту команду;
2 p q Переместить p во множество содержащее q. Если p и q уже в одном и том же множестве, игнорируйте эту команду;
3 p Вернуть количество и сумму элементов во множестве содержащем p.
Изначально имеется набор n множеств: {1}, {2}, {3}, ..., {n}.
Входные данные
Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа n и m (1 ≤ n, m ≤ 100000) - количество целых чисел и количество команд. Каждая из следующих m строк содержит команду. Для каждой операции 1 ≤ p, q ≤ n. Размер входного файла не превышает 5 МБ.
Выходные данные
Для каждой команды типа 3 выведите два целых числа: количество элементов и их сумму.
Пояснение
Изначально: {1}, {2}, {3}, {4}, {5}
После выполнения операции 1 1 2: {1,2}, {3}, {4}, {5}
После выполнения операции 2 3 4: {1,2}, {3,4}, {5} (мы опускаем пустое множество, которое получается при извлечении 3 из {3}
После выполнения операции 1 3 5: {1,2}, {3,4,5}
После выполнения операции 2 4 1: {1,2,4}, {3,5}
5 7 1 1 2 2 3 4 1 3 5 3 4 2 4 1 3 4 3 3
3 12 3 7 2 8