{"trustable":false,"sections":[{"title":"题面描述","value":{"format":"MD","content":"银河中有 $n$ 颗行星,许多双向的折跃通道连接着这些行星。6000年前,人皇在这些星球上进行了一次深度优先搜索,访问了这 $n$ 颗行星中的每一颗行星,并按照访问这些行星的顺序为这些行星编上了编号 $1$ 至 $n$ 。\n\n自那以后,很多的折跃通道渐渐失修损坏,至今仅剩下 $m$ 条折跃通道正常运作。人皇想要新建一些折跃通道,使得人皇从1号行星出发,可以按照 $1, 2, 3, \\dots , n$ 号行星的顺序,深度优先搜索地访问每一个行星,正如他6000年前所做的那样。\n\n请帮助人皇统计他至少需要新建几条折跃通道。"}},{"title":"输入格式","value":{"format":"MD","content":"输入第一行包括一个整数 $T$ 表示测试数据的数目;\n\n接下来,对于每组测试数据,第一行输入两个整数 $n$ 和 $m \\ (1 \\le n, m \\le 10^5)$ 表示行星和当下折跃通道的数量;\n\n接下来 $m$ 行,每行输入两个整数 $u_i$ 和 $v_i \\ (1 \\le u_i, v_i \\le n)$ 表示一条折跃通道连接 $u_i$ 和 $v_i$ 。\n\n保证所有测试数据的 $(n + m)$ 的总和不超过 $10^6$ 。"}},{"title":"输出格式","value":{"format":"MD","content":"对于每组测试数据,输出一行一个整数,表示人皇至少需要新建几条折跃通道。"}},{"title":"样例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\n3\n2 3\n1 1\n1 2\n2 1\n4 1\n1 4\n4 2\n1 2\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n\n0\n2\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}