题目描述

\(n\) 个岛国通过 \(n-1\) 座大桥连成一条线，我们把 \(n\) 个岛国从左往右依次编号 \(1 \sim n\)，那么第 \(i\) 座大桥就连接岛国 \(i\) 和岛国 \(i+1\)。

一年，在一些岛国之间发生了战争，具体来说，就是有 \(m\) 对岛国之间发生了战争。为了尽快平息战争，\(\text{OIers}\) 联合国准备切断一些桥梁，使得所有发生战争的两个岛国之间都无法连通。

\(\text{OIers}\) 联合国秘书长让你解决最少切断多少座大桥才能使所有发生战争的两个岛国之间都无法连通。

格式

输入格式

第一行两个整数 \(n\) 和 \(m\)，含义如题。

接下来 \(m\) 行，第 \(i\) 行两个整数 \(a_i\) 和 \(b_i\) 表示岛国 \(a_i\) 与 \(b_i\) 之间发生了战争。

输出格式

输出一行包含一个整数，表示最少需要切断的桥梁数。

样例1

输入样例1

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

输出样例1

2

样例解释

只需切断 \(2\) 座桥梁，可以切断第 \(4\) 座大桥（连接岛国 \(4\) 和 \(5\)）和第 \(7\) 座大桥（连接岛国 \(7\) 和 \(8\)）。

限制

\(100\%\)的数据：\(2 \le n \le 10^5, 1 \le m \le 10^5,1 \le a_i,b_i \le n\)，且所有\((a_i,b_i)\)互不相同。