某天小明邀请了许多朋友参加聚会，由于有些朋友之间互不认识，这些互不认识的人不愿意坐同一张桌，但是如果甲认识乙，且乙认识丙，那么甲和丙就算是认识的。请计算至少需要多少张桌子，才能让所有人都坐下来。

输入格式:

首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试首先输入两个整数n、m（1≤n，m≤1000），n表示朋友数，朋友从1到n编号，m表示认识关系数量。然后输入m行，每行两个整数A、B（A!=B），表示编号为A、B的两人互相认识。

输出格式:

对于每组测试，输出至少需要多少张桌子。

输入样例:

3

5 3

1 2

2 3

4 5

5 4

1 2

3 4

5 1

4 2

10 9

1 2

3 4

5 6

7 8

9 10

8 1

7 4

8 6

10 2

输出样例:

2

1

1

以下采用无向的邻接表解决问题

#include

using namespace std;

int main()

{

int t,n,m;

cin>>t;

for(int i=0;i

int sum=0;

cin>>n>>m;

vector people[n+1]; //people[i]存放与i认识的人

for(int j=0;j

int a,b;

cin>>a>>b;

people[a].push_back(b);

people[b].push_back(a);

}

bool arr[n+1];//arr[i]判断i是否被遍历过,false即未被循环遍历过,true即已被循环遍历过

fill(arr,arr+n+1,false);

queue> str; //用队列实现广度优先搜索(BFS)

for(int j=1;j<=n;j++){

if(arr[j]== false){//找到还没有桌子吃饭的人

arr[j]=true;

str.push(people[j]);

while(!str.empty()){//队列未空则同一桌的人已经访问结束

vector u=str.front();

str.pop();

for(int k=0;k

if(arr[u[k]]== false){//将与i认识的人(且未被访问过)入队列

arr[u[k]]=true;

str.push(people[u[k]]);

}

}

}

sum++;

}

}

cout<

}

return 0;

}