2185: 最小环数量

内存限制:512 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

给定 N 个点 M 条边的无向图,求最小环的数量。
注意:如果两个环由不同的边集组成,则视为不同的环。
例如环 3-1-2 和环 3-2-1 是同一个环,环 1-2-3 和环 2-3-1 也是同一个环。

输入格式

第一行包含两个整数 n 和 m,表示顶点的数量和边的数量。3 ≤ n ≤ 3000,3 ≤ m ≤ 6000。
接下来的 m 行,每行包含两个整数 ui 和 vi(1 ≤ ui ≠ vi ≤ n),表示 ui 和 vi 之间存在一条无向边。
图中不包含重边和自环,保证至少存在一个环,但不保证图连通的。

输出格式

输出一个整数表示答案。

输入样例 复制

样例1:
4 4
1 2
2 3
3 4
4 1

样例2:
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例3:
6 6
1 2
2 3
3 1
4 5
5 6
6 4

输出样例 复制

样例1:
1

样例2:
10

样例3:
2

数据范围与提示

来源:2022 NCPC