Надеюсь, Вы знаете красивую структуру 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}