Byteasar 国王统治着整个太阳系，其中包含 $n$ 颗行星。由于行星数量巨大，人们放弃了为行星命名的繁琐习俗，改用数字编号。因此，行星被方便地编号为 $1$ 到 $n$。Byteasar 的宫殿位于 $1$ 号行星，而他的军事基地位于 $2$ 号行星。很久以前，Byteasar 在这两颗行星之间建立了一个传送门，允许在两百五十分钟（略多于四小时）内往返于这两颗行星之间。

如今，传送技术已经更加成熟，最新的传送装置将旅行时间缩短到了仅需一小时。请注意，所有的传送门（无论是 Byteasar 的旧传送门还是市场上可用的新传送门）当然都是双向的，且传送时间与旅行距离无关。目前，系统中的一些行星已经通过这些新型传送门连接起来。事实上，现在已经可以在不使用国王私人传送门的情况下往返于 $1$ 号和 $2$ 号行星之间，尽管这需要经过多个其他传送门，因此速度并不比国王的私人传送门更快。Byteasar 认为这很幸运，因为他相信如果能更快地往返，将会构成安全漏洞。

传送技术本身正变得越来越普及，由于每个人都意识到了它的经济意义，每一对目前尚未直接连接传送门的行星都在申请建立连接。作为一位明智的统治者，Byteasar 打算在保证自身安全的前提下，尽可能多地批准这些建设申请，即不允许往返于 $1$ 号和 $2$ 号行星之间的速度快于他的私人传送门。请帮助国王确定他最多可以同意建设多少个传送门。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 40\,000$, $0 \le m \le 1\,000\,000$)，由一个空格分隔，分别表示 Byteasar 王国中的行星数量和现有的新型传送门数量。接下来的 $m$ 行描述了这些传送门。每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le n$)，由一个空格分隔，表示在 $a_i$ 和 $b_i$ 之间存在一个新型传送门。每对数字不会重复出现。你可以假设现有的新型传送门网络允许从 $1$ 号行星到达 $2$ 号行星，但所需时间不少于 250 分钟。

输出格式

程序应仅输出一个整数，即 Byteasar 在不破坏安全性的前提下可以同意建设的传送门的最大数量。

样例

输入 1

10 10
1 3
3 5
5 7
7 9
2 9
1 4
4 6
6 8
8 10
2 10

输出 1

10

现有传送门用实线标记，而 Byteasar 可以同意建设的传送门用虚线标记。