Problem 1177. -- 王侯第宅皆新主

1177: 王侯第宅皆新主

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 70  Solved: 5
[Submit][Status][Web Board]

Description

叶书生自从解出了玄宗的难题,一路飞黄腾达,像是加了高锰酸钾的过氧化氢。

由于叶书生升迁得太快,给主管人事的吏部尚书毕天柱(字朝梁)(号不朽栋栋)造成了很大的困扰。

忍无可忍的毕大人找到叶书生,请他为吏部的人事系统编写一套程序。

吏部的系统主要和大唐的“上清破云”超级计算机相连,最耗时的调动程序则需要由毕尚书手动计算并录入。

假设官员编号为1-n 开始的时候他们分别属于n个部门各自为政。

“上清破云”会发布三种命令:

 

“言有宗“格式:1 m n

将官员m及其部门所有人调至含有官员n的部门

“事有君格式:2 m n

将官员m调至含有官员n的部门

“唯无知” 格式 3 m

询问含有官员m的部门所拥有的员工总数和员工编号之和

 

对于命令12(“言有宗“和“事有君“)如果官员MN已经是一个部门的,那么不需要进行任何修改。

毕尚书是一个很牛逼的尚书,他可以接受c++TJOJ支持的代码,你只需要提交一份正确的代码并且通过TJOJ的测试,就可以去吏部领取五毛工资。

叶书生是不屑的,而你呢?

Input

输入仅一组数据

对于每一组数据,第一行输入两个整数NM(1<=Nm<=100000),表示有N个官员,共M次操作。

Output

对于每个命令3,输出两个数字,第一个表示含有官员m的部门所拥有的员工总数,第二个表示含有官员m的部门所拥有的员工编号之和。

Sample Input

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

Sample Output

3 12
3 7
2 8

HINT

最初:{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}

Source

[Submit][Status]