#CF977E. 联通环块

联通环块

题目描述

\hspace{15pt}给定一个有 nn 个顶点、mm 条边的简单无向图,顶点编号为 1∼n1\sim n。

\hspace{15pt}请统计整个连通块恰好是一个简单环的连通块数量。一个这样的连通块至少有 33 个顶点,可以将全部顶点按某个顺序排列,使块内的边恰好连接相邻顶点及首尾顶点,没有其他边。

\hspace{15pt}仅仅在连通块中找到一个环并不足够:若环上额外连着树枝,或块内还有其他边,则该连通块不计入答案。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(1\leqq n\leqq2\times10^5;\ 0\leqq m\leqq2\times10^5\right)$。

\hspace{15pt}此后 mm 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$,代表一条双向边。保证没有重边和自环。

输出格式

\hspace{15pt}输出一个整数,代表整个连通块恰好是简单环的块数。

测试样例

5 4
1 2
3 4
5 4
3 5
1

样例 1 解释

\hspace{15pt}顶点 {1,2}\{1,2\} 只形成一条边,不是环;顶点 {3,4,5}\{3,4,5\} 构成三角环,且没有额外的边,因此答案为 11。

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