← 返回题目列表

Codeforces · 1000/E

E. 我们需要更多的老板

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

你的朋友正在开发一款电脑游戏。他已经决定了游戏世界应该是什么样子——它应该由 $$$n$$$ 个位置组成,并通过 $$$m$$$ 双向通道连接。通道的设计方式应该是可以从任何位置到达任何其他位置。

当然,有些通道应该有怪物把守(如果你能毫无困难地到处走走,那就不好玩了,对吧?)。一些关键的通道将会被非常可怕的怪物守卫,需要英雄做好战斗准备并设计自己的策略来击败它们(通常这类怪物被称为boss)。你的朋友希望你帮助他安置这些老板。

游戏将从位置$$$s$$$开始并在位置$$$t$$$结束,但这些位置尚未选择。选择这些位置后,你的朋友将在每个通道中放置一个老板,这样如果不使用该通道就不可能从$$$s$$$到达$$$t$$$。你的朋友想要放置尽可能多的 Boss(因为更多的挑战意味着更多的乐趣,对吧?),所以他要求你帮助他确定最大可能的 Boss 数量,考虑到任何位置都可以选择 $$$s$$$ 或 $$$t$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$) — 分别是位置和段落的数量。

接下来是 $$$m$$$ 行,每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) 描述其中一个段落的端点。

保证不存在由两个或多个通道直接连接的位置对,并且可以从任何其他位置到达任何位置。

输出

打印一个整数 - 考虑到 $$$s$$$ 和 $$$t$$$ 的所有可能选择,你的朋友可以放置的 Boss 的最大数量。

示例

输入 #1

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

输出 #1

2

输入 #2

4 3
1 2
4 3
3 2

输出 #2

3