圈数统计

题目描述

给定一个简单无向图（不存在自环和重边），请统计这个图中有多少个简单环。环由三条或三条以上首尾相连的边构成。一个环称为简单环，是指没有点在环中出现两次。

注意，无向图没有方向，所以 $2 \to 3 \to 1 \to 2$ 和 $3 \to 2 \to 1 \to 3$ 是同一个环。

输入格式

第一行：两个整数 $n$ 和 $m$，表示图上的点数和边数； 第二行到第 $m+1$ 行：每行两个整数 $u$ 和 $v$ 表示图上有一条边连接 $u, v$ 两点。

输出格式

单个整数：表示给定的图上有多少不同的简单环。

数据范围

$0 \le m \le n(n-1)/2$； 对于 30% 的分数，$1 \le n \le 10$； 对于 100% 的分数，$1 \le n \le 20$。

样例输入 #1

3 3
1 2
2 3
1 3

样例输出 #1

1

样例输入 #2

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

样例输出 #2

3

知识点与难度

本题涉及的知识点从属于 GESP七级（图论、枚举），难度等级：⭐⭐⭐⭐。

测试点分布