题目描述

有 $N$ 个岛屿从西到东依次排列，通过 $N-1$ 条桥连接起来。

第 $i$ 条桥连接第 $i$ 个岛屿和第 $i+1$ 个岛屿。

一天，一些岛屿之间发生争执，岛屿居民提出了 $M$ 个请求：

请求 $i$：第 $a_i$ 个岛屿和第 $b_i$ 个岛屿之间发生争执。请使得这些岛屿之间的桥不能通行。

你决定移除一些桥来满足所有这 $M$ 个请求。

求必须移除的最少桥的数量。

约束条件

• 输入中的所有值都为整数。
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq a_i < b_i \leq N$
• 所有的 $(a_i, b_i)$ 对都是不同的。

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$

输出

输出必须移除的最少桥的数量。

示例输入 1

5 2
1 4
2 5

示例输出 1

1

通过移除连接第二个岛屿和第三个岛屿的桥，可以满足这些请求。

示例输入 2

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

示例输出 2

2

示例输入 3

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

示例输出 3

4