Almost Union-Find

题意翻译

有 $n$ 个集合,$m$ 次操作。规定第 $i$ 个集合里初始只有 $i$。有三种操作: 1. 输入两个元素 $p$ 和 $q$,若 $p$ 和 $q$ 不在一个集合中,合并两个元素的集合。 2. 输入两个元素 $p$ 和 $q$,若 $p$ 和 $q$ 不在一个集合中,把 $p$ 添加到 $q$ 所在的集合。 3. 输入一个元素 $p$,查询 $p$ 所在集合的元素个数和所有元素之和。 **【输入格式】** 有几组数据。 每组数据第一行输入 $n$ 和 $m$ 两个整数。 每组数据以下 $m$ 行,每行第一个数 $k$ 代表选择哪一个命令,若 $k$ 是 $1$ 或 $2$ 命令,则再输入两个整数 $p$ 和 $q$。若 $k$ 是 $3$,则输入一个整数 $p$。 输入文件结束符(EOF)结束输入。 **【输出格式】** 输出行数为每组数据 $3$ 号命令的总数。 每一行输出两个整数 $a$ 和 $b$,即元素个数和元素和。 **【数据范围】** $1 \leq n,m\leq 10 ^ 5$,$1 \leq p,q\leq n$。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3138 [PDF](https://uva.onlinejudge.org/external/119/p11987.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11987/26c36f66c6f7a4f753621f5225d4d163683ff773.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11987/a62dd792a69a4914dd19a578a5f43c1857d54517.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11987/71c634954dff55daeaad092e9a80a67b382b6644.png)

输入输出样例

输入样例 #1

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

输出样例 #1

3 12
3 7
2 8