德国有 \(N\) 个城市和 \(M\) 条双向道路。

德国人很讲究，德国的游览线路必须是一个 \(\texttt{BFS}\) 序，必须访问每个城市各一次，且满足以下条件：

• 首个城市可以任选；
• 除了首个城市外，每个城市被访问前至少有一个相邻城市已经被访问过；
• 每个城市与首个城市的距离单调不降。其中两个城市的距离定义为它们路径边数的最小值。

德芙有强迫症，一定要按照编号 \(1,2,\cdots,N\) 的顺序将每个城市访问一次。为了使这条游览线路符合德国人的要求，德芙需要先帮德国新修若干条道路。德芙想知道最少需要新修多少条道路。

第一行两个整数 \(N,M\) 。

接下来每行两个整数 \(a_i,b_i\) 表示一条双向道路。

输出一行一个整数，表示最少需要新修多少条道路。

样例2解释

一种符合要求的方式是，在城市 \(1,2\) 之间修一条路，在城市 \(1,4\) 之间修一条路。此时城市 \(1\) 与城市 \(1\sim 6\) 的距离分别是 \(0,1,1,1,2,2\) 。

数据范围

所有测试数据：
\(1\leq N\leq 200\;000\)
\(0\leq M\leq \min(200\;000,\;N(N-1)/2)\)
\(1\leq a_i,b_i\leq N\) 且没有重边和自环

官方数据太多，只放了少量极限数据，你可以自己 去下载 完整数据包自行评测