Description

Xiaoqiang wants to build a communication system across $N$ isolated planets. This communication system is a tree that connects $N$ nodes.

Edges of the tree are added one by one.

At any given time, the load of an edge is the number of simple paths in its current connected tree that pass through it.

For example, in the figure above, there are $5$ edges in total. The load of edge $(3, 8)$ is $6$, because there are six simple paths $2-3-8$, $2-3-8-7$, $3-8$, $3-8-7$, $4-3-8$, $4-3-8-7$ that pass through $(3, 8)$.

Now, as edges are added, your task is to dynamically answer Xiaoqiang’s queries about the load of certain edges.

Input Format

The first line contains two integers $N, Q$, the number of planets and the number of operations. Planets are numbered starting from $1$.

Each of the next $Q$ lines is in one of the following formats:

• A x y Add an edge between $x$ and $y$. It is guaranteed that $x$ and $y$ were previously disconnected.
• Q x y Query the load on edge $(x, y)$. It is guaranteed that there is an edge between $x$ and $y$.

Output Format

Output several integers, each being the answer to a query, one per line.

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

6

Hint

For all testdata, $1 \le N, Q \le 10^5$.

Translated by ChatGPT 5