#1612. E_1

E_1

说明

    为了完成离散作业,朱达远开始研究社交网络。他发现,在一个人群中,人与人之间有的存在着关系,有的没有关系,因而每个人都属于一个特定的社交圈。比如伟神与肖神有关系,伟神与果神有关系,我们可以认为肖神与果神间接有关系,他们三人属于一个社交圈。假如人群中还有小朱,小达,他们俩是好基友(存在关系),那么他俩属于另一个社交圈。如果一个人和任何人都没有关系,那么认为它属于一个自己的社交圈,这个社交圈里只有他一个人。
    不难发现,一些人在社交圈中起着关键作用,比如朱达远人脉很广,把妹众多,如果没有他,原本他所属的社交圈便会分解成好几个小的社交圈(这不就是离散数学中的割点么)。同时,一些关系也很重要,如果没有这些关系,原来的社交圈也会分解(当然这些关系就是割边啦)。
    现在,给定一个人群,以及其中的一些人与人之间的关系,根据给定的关系的先后顺序依次去掉这些关系,请编写程序求出每去掉一个关系剩下的社交圈的个数,这样朱达远就可以更好地了解哪些关系更重要了。

输入格式

    本题包含多组测试用例。在每组测试用例中,第一行为两个整数n和m,分别表示这个人群中有n个人,原本存在m个关系(2<=n<=100,1<=m<=500)。接下来的m行每行有两个整数x,y(1<=x<=n,1<=y<=n,x!=y)表示x与y有关系(将n个人分别按1,2,3......n-1,n标号,关系当然是双向的,并且两个人可能有多重关系)。

输出格式

    于每组测试用例,根据关系的输入顺序依次去掉每个关系并输出此时还存在几个社交圈(显然,当所有关系都删除后,还剩下n个社交圈)。对于每组测试数据用一行输出,细节详见Sample output。

样例

4 6
1 3
2 4
1 2
3 4
2 3
1 4
6 6
1 2
1 5
5 6
2 3
4 6
1 4
1 1 1 2 3 4
2 2 3 4 5 6

提示

1