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 unusable. 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:
20210326 10:44:59
Great problem on DSU. Answer the queries offline! 

jrseinc:
20200827 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:
20200804 07:51:14
Good DSU implementation problem. 

sudipandatta:
20200311 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:
20200223 21:16:08
A mustdo problem!! Last edit: 20200710 00:46:36 

nadstratosfer:
20190307 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 eurekamoment, still needed a few hours to figure out the math and how to design the code right. Quite an enjoyable AC. 

anshulwarade:
20180925 19:24:55
AC in one go! Nice problem, using DSU is enough!


cyber_sm0ke:
20180719 14:10:15
Cannot we use prism direclty ??


atharva_sarage:
20180712 20:08:12
Very nice DSU problem!! AC in single shot!! 

cnavneet:
20180711 22:26:30
Nice problem, reverse mst(union  find) 
Added by:  Aditya Muraletharan 
Date:  20130222 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  That would be me. 