你的朋友正在开发一款电脑游戏。他已经决定了游戏世界应该是什么样子——它应该由 $$$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