F. 热身运动

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

N颗行星由M条双向通道连接，这些通道可实现即时传送，且任意两颗行星之间始终可通过这些通道到达。若断开某一条通道即可使部分行星与其他行星隔离，则该通道被称为运输系统的桥。人们不喜欢被隔离，因此他们想知道：如果决定新建一条通道，系统中桥的数量最少可以是多少？注意：两颗行星之间可能存在多条通道。

多组测试数据。
每个测试用例以两个正整数 $N$ 和 $M$ 开头，表示行星数量和通道数量 $n \le 200000,m \le 1000000$ 。接下来M行，每行包含两个正整数A和B，表示系统中存在一条连接行星A和B的通道（行星编号为1~N）。

对于每个测试用例，输出新建一条通道后系统中桥的最少数目。