How Many Tables

Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input

The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input

Sample Output

2
4

这个题目是一个并查集问题（因为没有专门训练过所以我现在还不懂什么叫并查集）。

题目大致意思是，有n个客人，有m组两个客人之间的关系，代表两个客人之间相互认识，然后要给客人们安排桌子，客人们与其他人坐同一张桌子的条件是这张桌子上至少有一个人是他认识的，问你最少要安排多少张桌子。比如第一组样例，1和2认识，2又和3认识，那么1,2,3就可以坐同一张桌子，而4,5和1,2,3互相不认识，所以他们不能坐同一张桌子，而4,5相互认识，所以4和5可以坐同一张桌子，所以总共需要两张桌子。

所以我们不妨先给每个人安排一张桌子，桌子的标号就对应这个人的序号，然后再讨论有哪些桌子可以去掉。

若两个人认识，那么就可以让桌子减少一张，但是这个条件必须建立在这两个人原来不能坐同一张桌子的情况下，如果1认识2,同时2又认识3，这时候如果我告诉你1认识3，那么桌子数是不变的。

所以我们要判断的是两个人认识的情况下，他们本身是不是可以分为同一组，那么我们可以做一个类似链表的结构，如果1和2一组，那么让1指向2，如果2认识3，那么让2指向3，在这个情况下如果1又认识4，那么就找到1认识的最后一个人，并且让他认识4，也就是1->2->3->3,然后再让3->4.（这个可能是棵树吧。。不过渣渣没学过数据结构所以。。。用土鳖点的方法凑合吧）。但是如果是1认识3，那么1所在的组是1->2->3->3，而3所在的组是3->3，他们是同一组，所以就不用进行任何操作。

我们可以在每次链接两个人的时候减少一张桌子，也可以在所有的链接都完毕之后再数有多少个人坐的位置与他的标号相同（这就表示他从来没有与其他人链接过）
C++版本一

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;
const int N=10000+10;
int t,n,m,pre[N];
int find(int x){
    int r=x;
    while(pre[r]!=r)
        r=pre[r];

    return r;
}
void join(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        pre[fx]=fy;

}
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        int a,b;
        for(int i=1;i<=n;i++)
            pre[i]=i;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            join(a,b);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            if(pre[i]==i)
                ans++;

        cout << ans << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}