问题 E: 叠箱子

题目描述

小明去一家超市实习，在仓库里有一项工作是将很多到货但不上架的商品包装箱叠在一起，这样可以节约存储空间。为了方便作业，在同一天操作的时候，一旦一个箱子已经放到另一个箱子上，那么就不会再把这两个箱子分开。

一开始的时候一共有N个箱子，编号为1到N，所有盒子都是分开的，并没有叠在一起。

叠箱子的时候，小明会选择一个箱子X放到箱子Y上面。如果X已经和某些其他箱子叠在一起了，那么小明就会把这些箱子一起搬到Y上面。如果Y已经和其他箱子叠在一起了，假设Y在的那堆箱子最高的那个箱子是Z那么就把X那些箱子放到Z上面。

仓库负责人需要随时知道现在箱子的情况，所以他会时不时的来询问某一个箱子下面还有多少其他箱子这样的问题。

输入

第一行，两个整数N和Q，1<=n<=30000,<=Q<=100000

第二行到第Q+1行，每行描述一个事件，表示小明的一个移动操作，或者仓库负责人的一次查询，格式如下：

• M X Y：表示小明把X箱子放到了Y箱子的上面，1<=X,Y<=N,保证移动前X和Y不会在同一堆箱子里。

• C T：表示仓库负责人想知道T箱子的下方还有多少其他箱子，1<=T<=N。

输出

对每一个仓库负责人的查询，输出一行，一个整数表示正确答案。

感觉可以用并查集来做，但是不知道怎么算每个箱子下面有多少箱子。