分数: 300 点
问题陈述
给你一个无向连通图 N 顶点和 M 不包含自环和双边的边。
的
树的 i第边缘 (1 \leq i \leq M) 连接顶点 a_i 和顶点 b_i.
删除后断开图的边称为 桥.
找出作为桥的边的数量 M 边缘。
注释
- A 自循环 是一条边 i 这样 a_i=b_i (1 \leq i \leq M).
- 双边缘 是一对边 i,j 这样 a_i=a_j 和 b_i=b_j (1 \leq i<j \leq M).
- 无向图据说是 已连接 当每对顶点之间都存在路径时。
约束
- 2 \leq N \leq 50
- N-1 \leq M \leq min(N(N−1)⁄2,50)
- 1 \leq a_i<b_i \leq N
- 给定的图不包含自环和双边。
- 给定的图形已连接。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 : a_M b_M
输出
打印作为桥接的边的数量 M 边缘。
示例输入 1
7 7 1 3 2 7 3 4 4 5 4 6 5 6 6 7
示例输出 1
4
下图显示了给定的图表:
以红色显示的边缘是桥。他们有四个。
示例输入 2
3 3 1 2 1 3 2 3
示例输出 2
0
可能没有桥。
示例输入 3
6 5 1 2 2 3 3 4 4 5 5 6
示例输出 3
5
每条边都有可能是一座桥。