问题 4787 --魔法循环

4787: 魔法循环★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 55  解决: 26
[提交][状态][命题人:]

题目描述

炎炎夏日,鹏鹏要修炼进阶魔法了。他需要剔除魔法网络中不合法的部分。

魔法网络可以被认为是一张无向图。而当且仅当一个连通块中所有魔法节点的度数为2时,这个连通块被认为是合法的。

现在,你需要帮助鹏鹏数数,魔法网络中有多少合法的连通块。

比如上述图中,一共有6个连通块,其中有2个是合法的。

分别是{7,10,16},{5,11,9,15}

输入

第一行两个整数,n和m,分别代表节点的数量和无向图的边的数量。其中(1≤n≤2e5,0≤m≤2e5)

下面的m行,每行2个整数vi,ui(vi不等于ui),表示vi和ui之间有一条边

输出

输出一个整数,代表合法连通块的数量。
样例输入
Copy
5 4
1 2
3 4
5 4
3 5
样例输出
Copy
1

提示

样例2输入

17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6

样例2输出

2

注释:

1)样例1中,{3,4,5}是合法的

2)样例2和题目中的图吻合

来源

[提交][状态]