{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/MARCH14/mandarin/GERALD07.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/MARCH14/russian/GERALD07_new.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\u003ch3\u003eProblem Statement\u003c/h3\u003e\r\n\u003cp\u003eChef has a 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 an unique index from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e, also each edge of the graph has an unique index from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eM\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eAlso Chef 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, Chef wants to know: how many connected components will contain graph \u003cb\u003eG\u003c/b\u003e if Chef 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 Chef with these queries. \u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe 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.\u003c/p\u003e\r\n\r\n\u003c/p\u003e\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each query of each test case print the required number of connected components.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e.\u003c/li\u003e\r\n\u003cli\u003e\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\r\n\u003cli\u003e\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\r\n\u003cli\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.\u003c/li\u003e\r\n\u003cli\u003eSum 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.\u003c/li\u003e\r\n\u003cli\u003eGraph \u003cb\u003eG\u003c/b\u003e can contain self-loops and multiple edges.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n2\r\n3 5 4\r\n1 3\r\n1 2\r\n2 1\r\n3 2\r\n2 2\r\n2 3\r\n1 5\r\n5 5\r\n1 2\r\n1 1 1\r\n1 1\r\n1 1\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n2\r\n1\r\n3\r\n1\r\n1\r\n\u003c/pre\u003e"}}]}