Dynamic Edge Load Queries in a Growing Tree

Xiao Qiang is constructing a communication system on N isolated planets. This system is a tree connecting N nodes. The tree is built by adding edges one by one. At any moment, the load of an edge is defined as the number of simple paths in the current connected component (tree) that pass through that edge. In a tree, since there is a unique simple path between every two nodes, if removal of an edge divides its connected component into two parts with n₁ and n₂ nodes respectively, then the load of that edge is given by the formula:

[ \text{load} = n_{1} \times n_{2} ]

Your task is to process a sequence of operations. There are two types of operations:

• A u v: Add an edge connecting nodes u and v (1-indexed). It is guaranteed that adding the edge does not form a cycle (i.e. it connects two different trees in the forest).
• Q u v: Query the current load of the edge connecting nodes u and v. It is guaranteed that this edge has already been added.

Note that as more edges are added, previously added edges may have their load change because their removal splits a larger tree. Your program must process the operations in order and output the answer for each query.

inputFormat

The first line contains two integers N and M where N is the number of nodes and M is the number of operations.

Each of the next M lines contains an operation in one of the following two formats:

• A u v: Add an edge between nodes u and v.
• Q u v: Query the load of the edge between nodes u and v.

It is guaranteed that the operations occur in a valid order, i.e. a query will refer only to an edge that has already been added.

outputFormat

For each query operation, output a single integer representing the current load of the specified edge.

sample

5 7
A 1 2
A 2 3
Q 1 2
A 2 4
Q 2 3
A 4 5
Q 2 4

2
3
6