Chef and Graph Queries

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Problem Statement
Chef has a undirected graph G. This graph consists of N vertices and M edges. Each vertex of the graph has an unique index from 1 to N, also each edge of the graph has an unique index from 1 to M.
Also Chef has Q pairs of integers: L_{i}, R_{i} (1 ≤ L_{i} ≤ R_{i} ≤ M). For each pair L_{i}, R_{i}, Chef wants to know: how many connected components will contain graph G if Chef erase all the edges from the graph, except the edges with indies X, where L_{i} ≤ X ≤ R_{i}. Please, help Chef with these queries.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three integers N, M, Q. Each of the next M lines contains a pair of integers V_{i}, U_{i}  the current edge of graph G. Each of the next Q lines contains a pair of integers L_{i}, R_{i}  the current query.
Output
For each query of each test case print the required number of connected components.
Constraints
 1 ≤ T ≤ 1000.
 1 ≤ N, M, Q ≤ 200000.
 1 ≤ U_{i}, V_{i} ≤ N.
 1 ≤ L_{i} ≤ R_{i} ≤ M.
 Sum of all values of N for test cases is not greater than 200000. Sum of all values of M for test cases is not greater than 200000. Sum of all values of Q for test cases is not greater than 200000.
 Graph G can contain selfloops and multiple edges.
Example
Input: 2 3 5 4 1 3 1 2 2 1 3 2 2 2 2 3 1 5 5 5 1 2 1 1 1 1 1 1 1 Output: 2 1 3 1 1
Author:  gerald 
Editorial  http://discuss.codechef.com/problems/GERALD07 
Tags  decomposition, gerald, linkcuttree, march14, mediumhard 
Date Added:  9022014 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
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. 