问题 H: 蛤玮的机房

问题 H: 蛤玮的机房

时间限制: 1 Sec  内存限制: 128 MB
提交: 587  解决: 242
[状态] [讨论版] [提交] [命题人:]
题目描述
蛤玮成为了实验室主任,现在学校要求他建好一个机房里的通信网络.这个网络中有n台主机,现在已知建设好了m条线路,可以让一些主机直接或间接通信,为了使这n台主机互相之间都可以直接或间接通信,请问蛤玮最少还需建设多少条线路。
间接通信指:若A,B可以直接通信,B,C可以直接通信,则A,C可以间接通信,同理若C,D可以直接通信,A,D也可以间接通信。
输入

输入第一行为一个整数T(1<=T<=10),代表数据组数。对于每组数据,第一行为两个整数n(1<=n<=100),m(1<=m<=n*n),接下来m行每行两个整数u,v(1<=u,v<=n),表示主机u,v之间已建立线路。

输出

对于每组数据,输出一个整数,表示还需建设的线路数。

样例输入 Copy
1
3 3
1 1
2 1
1 2
样例输出 Copy
1