### 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

### Compile Errors

Time Limit: 1 Seconds
Memory Limit: 512MB
No. of ACs: 3
Your best score: 0
Source: LOJ #2230