NITTROAD - Roads of NITT



The Institute of NITT believes in frugality. So when they made the plan for interconnecting the N hostels, they decided to construct as few bidirectional roads as possible. The hostels are interconnected with roads in such a way that every pair of hostels is connected by exactly one path.
Moreover, they were so frugal that they used low quality tar in making the roads. As a result, the roads start to crack and cannot be used anymore.
Now Alpa has a set of queries. At the time of each query, he knows the roads that are un-usable. He wants to find the number of pairs of hostels that are disconnected, i.e, the number of pairs (x,y) such that 1 <= x < y <= N and there exists no path between hostels x and y.
Help him find the result for each query.


The Institute of NITT believes in frugality. So when they made the plan for interconnecting the N hostels, they decided to construct as few bidirectional roads as possible. The hostels are interconnected with roads in such a way that every pair of hostels is connected by exactly one path.


Moreover, they were so frugal that they used low quality tar in making the roads. As a result, the roads start to crack and cannot be used anymore.


Now Alpa has a set of queries. At the time of each query, he knows the roads that are un-usable. He wants to find the number of pairs of hostels that are disconnected, i.e, the number of pairs (x,y) such that 1 <= x < y <= N and there exists no path between hostels x and y.


Help him find the result for each query.


Constraints:


Test cases <= 5

No. of hostels, N <= 20000

No. of queries, Q <= 20000



Input


First line contains t, the total test cases.

Each test case looks  as follows:

First line contains N, total number of hostels.

Next N - 1 lines contain two integers x and y, indicating that there is a road  between x and y. (1 <= x < y <= N). The roads are numbered from 1 to N - 1.

Next line contains Q, total number of queries.

Next Q lines contain the Q queries.

Each query may be of the following two forms:

R x - Remove the road numbered x. It is guaranteed that this road existsand hasn't already been removed.

Q - Output the total number of pairs (x, y) such that 1 <= x < y <= N and there exists no path between hostels x and y.


Output

For each test case,

Output a line for each query with the required value.

Print a blank line after each test case.

 

Example

Input:
2

3
1 2
1 3
5
Q
R 1
Q
R 2
Q

4
1 2
1 3
1 4
7
Q
R 1
Q
R 2
Q
R 3
Q

Output:
0
2
3

0
3
5
6

 




hide comments
sumeghtechie: 2018-06-29 11:54:03

If you are getting WA , you might be printing the array combining all test cases together...Don't do so.. Print for each test case simultaneously as you proceed..This will give AC as it did for me.

pshishod2645: 2018-06-21 20:50:01

Now I realised why mst tag is there!

siva2697: 2018-03-26 10:08:00

Nice Problem.MUST DO

amulyagaur: 2017-12-06 10:01:15

250 comes up with such a nice problem! :))

amb1151: 2017-12-03 15:00:20

Can anyone give a hint on how to solve this problem?...

jayantisswani: 2017-09-30 14:35:40

Do all the vertices become disconnected after executing all the queries ?

babur: 2017-06-28 05:49:59

Think Reverse....a must do problem

Vipul Srivastava: 2016-12-14 16:14:14

Couldn't think of the approach myself. A great question to learn new things. If you can't think of the solution by yourself do take help don't leave this question.

mahmud2690: 2016-10-17 09:51:37

Nice problem!

nsitsk: 2016-10-12 19:00:45

Awesome problem :)
Got to learn something new.


Added by:Aditya Muraletharan
Date:2013-02-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:That would be me.