Майже Union-Find#2047
Сподіваюся, ви знайомі з елегантною структурою даних Union-Find. У цій задачі вам потрібно реалізувати щось схоже, але не зовсім те саме.
Структура даних, яку потрібно реалізувати — це набір неперетинних множин, який підтримує три операції:
1 : Об'єднати множини, які містять та . Якщо та вже перебувають в одній множині, цей запит ігнорується;
2 : Перемістити у множину, яка містить . Якщо та вже перебувають в одній множині, цей запит ігнорується;
3 : Вивести кількість елементів та суму елементів у множині, яка містить .
Спочатку існує множин: \{1\}, \{2\}, \{3\}, \ldots, \{n\}.
Кілька тестових випадків. Кожен тестовий випадок починається з рядка з двома цілими числами та (1 \leq n, m \leq 100000) — кількість чисел та кількість команд. Кожен з наступних рядків містить одну команду. Для кожної операції 1 \leq p, q \leq n. Розмір вхідного файлу не перевищує МБ.
Для кожної команди типу вивести два цілих числа: кількість елементів та їхню суму.
Приклад 1
Спочатку: \{1\}, \{2\}, \{3\}, \{4\}, \{5\}
Після операції 1 1 2: \{1,2\}, \{3\}, \{4\}, \{5\}
Після операції 2 3 4: \{1,2\}, \{3,4\}, \{5\} (ми ігноруємо порожню множину, що утворюється після вилучення з )
Після операції 1 3 5: \{1,2\}, \{3,4,5\}
Після операції 2 4 1: \{1,2,4\}, \{3,5\}