运送物资

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

A地区发生了洪灾,造成部分道路被毁,通信中断。为了先安顿受灾群众,政府决定利用船只向各个灾民聚集区域运送救灾物资。已知A地区共有居民居住点N个,编号为1-N,受灾后经过卫星拍摄的图片发现还有M条道路可用,并且两个居民居住点之间可能有多条道路相连,也可能无路可通。有道路相连的居民居住点可以认为是一个灾民聚集区域,因为在这个区域内部还可以使用陆地交通工具进行物资的交换。由于洪灾发生的太突然,所有的人员都没有来得及转移,也就是说A地区所有居民居住点都有居民被困。为了尽快完成任务,政府需要知道至少需要多少船只,才能保证每个灾民聚集区域都有船只去解救。

Input

第一行是一个整数T,表示有T组测试样例(0 < T <= 50)。每个测试样例开始一行包括两个整数N,M,(0 < N <= 20,0 <= M <= 200)分别代表A地区有N个居民居住点,和M条保留下来的道路。下面的M行,每行有两个整数u,v,表示居民点u,v仍然有道路相连。保证u,v都在1-N的范围内,并且u ≠ v。

Output

每个测试样例输出一行,包括一个整数,即至少需要多少船只,才能保证每个灾民聚集区域都有船只去解救。

Sample Input

2
3 1
1 2
3 2
3 2
1 2

Sample Output

2
1

Hint

 

Source

山东理工大学第三届ACM程序设计竞赛