#CF977E. 联通环块
联通环块
题目描述
给定一个有 个顶点、 条边的简单无向图,顶点编号为 。
请统计整个连通块恰好是一个简单环的连通块数量。一个这样的连通块至少有 个顶点,可以将全部顶点按某个顺序排列,使块内的边恰好连接相邻顶点及首尾顶点,没有其他边。
仅仅在连通块中找到一个环并不足够:若环上额外连着树枝,或块内还有其他边,则该连通块不计入答案。
输入格式
第一行输入两个整数 $n,m\left(1\leqq n\leqq2\times10^5;\ 0\leqq m\leqq2\times10^5\right)$。
此后 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$,代表一条双向边。保证没有重边和自环。
输出格式
输出一个整数,代表整个连通块恰好是简单环的块数。
测试样例
5 4
1 2
3 4
5 4
3 5
1
样例 1 解释
顶点 只形成一条边,不是环;顶点 构成三角环,且没有额外的边,因此答案为 。
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