CF129B Students and Shoelaces

题目描述

小贝和小聪是俱乐部的管理人员。当俱乐部聚会时,学生们又开始捣乱。他们带来很多鞋带,并且用鞋带将大家相互捆绑起来,每根鞋带捆住两个学生。 为了恢复秩序,小贝和小聪采取了以下措施。首先,对于每位学生,小贝检查他和哪些学生捆在一起。如果和这个学生捆在一起的学生人数等于1,小贝就将这个学生记录在案。小贝检查完每位学生后,小聪就将这些被记录的学生分到一个组中,并将这组学生踢出俱乐部。这组学生立刻离开俱乐部,同时将捆着他们的鞋带也一起带走。这组学生离开后,小贝和小聪继续重复上述的过程,直到没有学生可以被记录下来为止。 请确定总共有多少组学生被踢出俱乐部。

输入格式

第一行包含两个整数n和m分别表示刚开始的学生数量和鞋带数量(![图片](http://codeforces.com/predownloaded/71/d0/71d028b02d9dc63a3c5b31c7dff711ec27569a4c.png))。学生们从1到n进行编号,鞋带从1到m进行编号。接下来m行,每行包含两个整数a和b,表示被第i根鞋带捆住的两位学生的编号(1 ≤ a, b ≤ n, a ≠ b)。输入保证没有一对学生被多于一根的鞋带捆住。

输出格式

输出一个整数,表示被踢出俱乐部的学生组数。

说明/提示

在第一个样例中,小贝和小聪不会踢掉任何学生,因为每位学生都和另外两位学生捆在一起。 在第二个样例中,有4名学生依次捆成一条“链”,还有2名学生没有被捆。小贝和小聪会先将“链”两端的学生(1号和4号)作为一组踢走,再将2号和3号作为一组踢走,所以答案为2。 在第三组样例中,除了4号学生,其他学生会作为一组一起被踢走,所以答案为1。