{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Lily has an undirected graph \u003cb\u003eG\u003c/b\u003e. This graph consists of \u003cb\u003eN\u003c/b\u003e vertices and \u003cb\u003eM\u003c/b\u003e edges. Each vertex of the graph has a unique index from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e, also each edge of the graph has a unique index from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eM\u003c/b\u003e.\n\nAlso Lily has \u003cb\u003eQ\u003c/b\u003e pairs of integers: \u003cb\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e (\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e). For each pair \u003cb\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, Lily wants to know: how many connected components will graph \u003cb\u003eG\u003c/b\u003e contain if Lily erase all the edges from the graph, except the edges with indies \u003cb\u003eX\u003c/b\u003e, where \u003cb\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eX\u003c/b\u003e ≤ \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. Please, help Lily with these queries. \n "}},{"title":"Input","value":{"format":"MD","content":"The first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003cbr\u003eThe first line of each test case contains three integers \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eM\u003c/b\u003e, \u003cb\u003eQ\u003c/b\u003e. Each of the next \u003cb\u003eM\u003c/b\u003e lines contains a pair of integers \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eU\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - the current edge of graph \u003cb\u003eG\u003c/b\u003e. Each of the next \u003cb\u003eQ\u003c/b\u003e lines contains a pair of integers \u003cb\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - the current query."}},{"title":"Output","value":{"format":"MD","content":"For each query of each test case print the required number of connected components.\n\n "}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre\u003e2\n3 5 4\n1 3\n1 2\n2 1\n3 2\n2 2\n2 3\n1 5\n5 5\n1 2\n1 1 1\n1 1\n1 1\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre\u003e2\n1\n3\n1\n1\n\u003c/pre\u003e"}},{"title":"Constraints","value":{"format":"MD","content":"\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e.\u003c/li\u003e \n\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eM\u003c/b\u003e, \u003cb\u003eQ\u003c/b\u003e ≤ \u003cb\u003e200000\u003c/b\u003e.\u003c/li\u003e \n\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eU\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e.\u003c/li\u003e \n\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e.\u003c/li\u003e \n\nSum of all values of \u003cb\u003eN\u003c/b\u003e for test cases is not greater than \u003cb\u003e200000\u003c/b\u003e. Sum of all values of \u003cb\u003eM\u003c/b\u003e for test cases is not greater than \u003cb\u003e200000\u003c/b\u003e. Sum of all values of \u003cb\u003eQ\u003c/b\u003e for test cases is not greater than \u003cb\u003e200000\u003c/b\u003e.\n\nGraph \u003cb\u003eG\u003c/b\u003e can contain self-loops and multiple edges."}}]}