Game Revisited

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Hussain and Alex are exIOI participants. They participated together in IOI 2014, aiming for medals. Unfortunately both had very bad luck back then and neither of them got a medal. (Even though IOI 2014 tasks were very interesting and not so hard).
Hussain and Alex felt very annoyed after that. Every time they come across any of the IOI 2014 problems, they just feel angry and each says to himself, "How didn't I solve this task?!".
Last week they came across the problem Game from IOI 2014 which was a really easy problem. Hussain again felt very angry, till the point that he thought of a much harder version of this task and decided to solve it.
Basically IOI 2014 game was a game played between two playersand an undirected graph consisting of N nodes.
Hussain will give Alex a list of bidirectional edges. This list contains M edges numbered from 1 to M.
Alex will add these edges one by one starting from edge number 1.
While adding these edges to the graph, whenever the entire graph became connected (ie. it's possible to move between any 2 of the N nodes via a sequence of the added edges), the game stops and Alex tells Hussain the number of edges he has added till then.
Hussain decided to make the game more challenging, and so he told Alex that he will play on the same list of edges Q times, each time taking the current list and swapping 2 edges in this list and giving it back to Alex. Each time, Alex must tell the number of edges he will add till the graph becomes connected.
Of course playing each game edge by edge is killing. Help Alex to play with Hussain fast. Please note that after a game finishes, Alex returns the list to Hussain, and Hussain swaps another pair of edges without changing the order of the remaining edges in the list. That is, the swaps are not reverted and the edges which were swapped in a query remain swapped for the future queries as well.
Also note that you do not need to report what happens with the original graph. Only after each query.
Input
 First line of each testfile contains a single integer T, denoting the number of testcases.
 First line of each testcase contains 3 space separated integers N,M,Q, denoting the number of nodes, the number of edges in the list and the number of queries to process.
 Next M lines specifying the edges in the original list. The ith line of them would contain two space separated integers U_{i} , V_{i} . U_{i} , V_{i} denoting the endpoints of the ith edge. It's guaranteed that the list won't contain a self loop (an edge between a node and itself), but it may contain edges between the same pair of nodes.
 Next Q lines each contain 2 space separated integers a , b denoting the indexes of edges Hussain should swap.
Output
For each testcase, output Q lines, the ith line of them must contain a single integer denoting the number of edges Alex must insert so the graph becomes connected.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N , Q ≤ 100000
 N  1 ≤ M ≤ 100000
 1 ≤ U_{i}, V_{i} ≤ N
 For each query 1 ≤ a,b ≤ M , a != b
 The sum of N in all scenarios won't exceed 100000
 The sum of M in all scenarios won't exceed 100000
 The sum of Q in all scenarios won't exceed 100000
 It's guaranteed that the graph becomes connected if Alex adds all edges in every scenario
Example
Input: 1 5 7 3 1 2 1 3 2 3 3 5 1 5 4 5 1 4 5 6 3 4 7 4 Output: 5 5 4
Explanation
The original list of edges is { (1, 2), (1, 3), (2, 3), (3, 5), (1, 5), (4, 5), (1, 4) }.
First query: After applying the (5, 6) swap, the list of edges is { (1, 2), (1, 3), (2, 3), (3, 5), (4, 5), (1, 5), (1, 4) }. Just the first 5 edges in this, that is { (1, 2), (1, 3), (2, 3), (3, 5), (4, 5) } connects the entire graph. Hence the answer is 5.
Second query: After applying the (3, 4) swap to the list from the previous query, we get { (1, 2), (1, 3), (3, 5), (2, 3), (4, 5), (1, 5), (1, 4) }. Just the first 5 edges in this, that is { (1, 2), (1, 3), (3, 5), (2, 3), (4, 5) } connects the entire graph. Hence the answer is 5.
Third query: After applying the (7, 4) swap to the list from the previous query, we get { (1, 2), (1, 3), (3, 5), (1, 4), (4, 5), (1, 5), (2, 3) }. Just the first 4 edges in this, that is { (1, 2), (1, 3), (3, 5), (1, 4) } connects the entire graph. Hence the answer is 4.
Author:  deadwing97 
Tags  deadwing97 
Date Added:  2062017 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 