11987 - Almost 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}.

Input

輸入有多組測試資料，每組資料一開始給定兩個整數 n, m (1 <= n, m <= 100,000)，n 表示一開始的集合數，m 表示操作的指令數，接下來的 m 列每列一道指令，指令滿足 1 <= p, q <= n。輸入資料大小最多5MB，並以EOF表示結束。

Output

當遇到第三種操作指令的時候，輸出兩個整數分別表示元素個數與元素總和。

Sample Input

5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3

Output for the Sample Input

3 12
3 7
2 8

Explanation

一開始: {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}

---

原文出處