该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Friendship

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

The friend-ship usually sinks easily.

There are $n$ students lining up from west to east and between the $i$-th$(1 \leq i<n)$ student and the $(i+1)$-th student there is a friendship chain at first.

We define if $a$-th student and $b$-th student are not friends, if and only if there exists no friendship chain between the $c$-th $(c\in[a,b))$ student and the $(c+1)$-th student. It is clear that all the students are friends in the beginning.

One day, $m$ fights took place among these students. Here we define fight as follows:

A fight $i$ took place between only two students, the $a_i$-th student and $b_i$-th student, so $a_i$-th student and $b_i$-th student are not friends any more.

To meet all these $m$ fights you need to break some friendship chains. Print the minimum number of friendship chains that must be broken.

Input

The first line contains two integers $n,m(2\leq n\leq 10^5,1\leq m\leq 10^5)$ denoting the number of students and fights.

In the following $m$ lines, each line contains two integers $a_i,b_i(1\leq a_i<b_i\leq n)$ denoting the $i$-th fight between the $a_i$-th students and the $b_i$-th student. It is guaranteed that all pairs $(a_i,b_i)$ are distinct.

Output

Print a single integer, denoting the answer to the question.

5 2
1 3
2 5

1

Notes

The requests can be met only by breaking the friendship chain between the second student and the third student.