Майже Union-Find

Сподіваюся, ви знайомі з елегантною структурою Union-Find. У цій задачі вам потрібно реалізувати щось подібне, але не зовсім таке ж.

Структура даних, яку ви маєте створити, представляє собою набір неперетинних множин, що підтримують три операції:

• 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}