← 返回题目列表

AtCoder · abc075_c

C. 桥

中文机器翻译题面 查看原题

分数: 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

下图显示了给定的图表:

570677a9809fd7a5b63bff11e5d9bf79.png

以红色显示的边缘是桥。他们有四个。


示例输入 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

每条边都有可能是一座桥。