greatmerge

The Great Merge

Xiaoqiang wants to establish a communication system between \(N\) currently isolated planets, numbered \(1\) to \(N\). The system will be made out of \(N - 1\) data links each allowing communication between a pair of planets, and shall form a tree over which any two planets can communicate via some sequence of links.

These data links will be constructed one-by-one. At any point in time, the load of a data link is the number of simple paths across planets and data links which traverse it.

For example, in the scenario above with 8 planets and 5 links constructed, the load on the data link \((3, 8)\) is 6. The 6 simple paths traversing \((3, 8)\) are \(2 - 3 - 8\), \(2 - 3 - 8 - 7\), \(3 - 8\), \(3 - 8 - 7\), \(4 - 3 - 8\), and \(4 - 3 - 8 - 7\).

Your task is to answer Xiaoqiang's queries about the load of various data links as the system progressively gets constructed.

Input format

The first line of input consists of two integers \(N\) and \(Q\), respectively denoting the number of planets and the number of operations which will occur.
\(Q\) lines of input follow. Each line will be in one of the following two formats:

• A \(x\) \(y\): A data link is constructed between planets \(x\) and \(y\). It is guaranteed that \(x\) and \(y\) were not previously connected directly or indirectly by data links.
• Q \(x\) \(y\): Find the load of the data link between planets \(x\) and \(y\). It is guaranteed that such a data link currently exists.

Output format

Output one line for each query operation - containing a single integer, the load of the requested data link.

Limits

\(1 \leq N, Q \leq 10^5\).

Subtask #	Score	Constraints
1	10	\(1 \leq N, Q \leq 150\)
2	25	\(1 \leq N, Q \leq 2000\)
3	65	No additional constraints

Samples

Sample Input 1	Sample Output 1
8 6 A 2 3 A 3 4 A 3 8 A 8 7 A 6 5 Q 3 8	6