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
karelisp: 2021-03-26 10:44:59

Great problem on DSU. Answer the queries offline!

jrseinc: 2020-08-27 18:35:44

such beauty. I enjoyed solving this problem and I will highly recommend it. It is a bit complex for beginners cause the solution I went for used offline programming and DSU so if you don't know these you will find it a bit tough. But please don't skip this question. Learned a lot for it.

vineetjai: 2020-08-04 07:51:14

Good DSU implementation problem.

sudipandatta: 2020-03-11 19:10:29

Awesome!!! I couldn't solve it on my own. But this a really beautiful and tricky problem. Do not skip this.

kushagra_2: 2020-02-23 21:16:08

A must-do problem!!

Last edit: 2020-07-10 00:46:36
nadstratosfer: 2019-03-07 20:55:02

Woke up yesterday with a solution to a problem, but had no idea which one! Turns out I had looked at this one, clueless, about a month ago, and irritated my subconscious enough to get the wheels turning. Aside of the eureka-moment, still needed a few hours to figure out the math and how to design the code right. Quite an enjoyable AC.

anshulwarade: 2018-09-25 19:24:55

AC in one go! Nice problem, using DSU is enough!

cyber_sm0ke: 2018-07-19 14:10:15

Cannot we use prism direclty ??

Direct MST I mean ?

atharva_sarage: 2018-07-12 20:08:12

Very nice DSU problem!! AC in single shot!!

cnavneet: 2018-07-11 22:26:30

Nice problem, reverse mst(union - find)


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.