说明

在原始部落中，由于食物缺乏，部落居民经常因为争夺猎物发生冲突，几乎每个居民都有自己的仇敌。部落酋长为了组织一支保卫部落的卫队，希望从居民中选出最多的居民加入卫队，并保证卫队中任何两个人都不是仇敌。假设已给定部落中居民间的仇敌关系图，编程计算构建部落护卫队的最佳方案。

输入格式

第一行是一个整型数m(m<100)表示共有m组测试数据。

每组测试数据第一行输入部落人数n和人与人之间的关系数c（1<=n<=100,1<=c<=10000）。

接下来有c行，每行输入两个数，代表有友好关系的两个人序号u,v（1<=u，v<=100）。

输出格式

对于每一组输入，输出部落护卫队的最大人数。 每组的输出占一行。

样例

2
5 8
1 2
1 3
1 4
1 5
2 3
3 4
3 5
4 5
4 5
1 2
1 4
2 3
2 4
3 4

4
3

来源

《趣学算法》5.3节