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

Anant Upadhyay: 2016-08-29 17:16:11

Certainly one of the finest graph problem !

sbansalcs: 2016-08-09 08:26:03

Anyone has an online solution?

hodobox: 2016-07-24 01:54:34

Enjoyed :)

ASHUTOSH DWIVEDI: 2016-06-21 23:45:25

'Kudos' to the problem setter :)

shikhar0037: 2016-05-21 13:07:02

One of the finest graph problem . AC in 1 go :)

torque: 2015-12-30 13:00:33

Great problem!!


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