题目描述

有一张初始没有边的 $n$ 个点的图，现在需要支持以下两种操作：

• A x y，加入一条连接 $x,y$ 的边，保证 $x,y$ 不在同一连通块且此操作恰好出现 $n-1$ 次；
• Q，询问此时若在 每个连通块 里选择一个关键点，并记录 $d_u$ 表示 $u$ 到所在连通块的关键点的距离时，$\sum_{i=1}^n d_i$ 的最小值，距离指路径上经过的边的数量。

每次询问独立。

输入格式

第一行两个整数 $n,m$ 表示点的数量和操作数。

接下来 $m$ 行，每行一个操作，格式见题目描述。

输出格式

对于每个询问，输出一行一个整数表示答案。

8 10
Q
A 1 2
A 4 5
A 6 7
A 3 4
Q
A 2 5
A 6 8
A 4 6
Q

0
4
12

样例解释

对于第一次询问，所有点互不联通，每个点都设为关键点，答案是 $0$；

对于第二次询问，设置关键点为 $4,7,8$，答案是 $4$；

对于第三次询问，设置关键点为 $4$，答案是 $12$。

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 4\times 10^4$，$1\leq m\leq 8\times 10^4$。