| 问题描述 |
|---|
大海上有m座岛屿，岛屿编号分别是1、2、3、...、m，岛屿和岛屿之间通过桥梁进行连接，有的岛屿之间有桥梁，有的岛屿之间没有桥梁，但可以经由通往别的岛屿的桥梁绕行到目的岛屿。如果完全无法通行，只能租用水上飞机才能到达该岛屿。LYF住在第1座岛屿，他想游历一遍所有的岛屿，并且最终回到第1座岛屿，问他至少需要租用多少次水上飞机？ |
| 输入描述 |
多组案例。一个正整数n，表示案例的数量。（n<=100） 每组案例先是两个正整数m和p，分别表示岛屿数量和桥的数量，（m<=100，p<=m(m-1)/2） 然后是p行数据，每行数据由两个正整数a和b组成，表示第a座岛屿和第b座岛屿之间有桥梁。（1<=a,b<=m） |
| 输出描述 |
针对每组案例，输出一个整数，表示需要租用水上飞机的次数。 每组案例输出完都要换行。 |
| 样例输入复制样例 |
2 3 2 1 2 1 3 4 1 1 2 |
| 样例输出 |
0 3 |
| 相关 |