#P2022I. Friendship

    ID: 120 Type: Default 1000ms 256MiB Tried: 18 Accepted: 6 Difficulty: 8 Uploaded By: Tags>福建师范大学第19届程序设计竞赛

Friendship

Friendship

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

The friend-ship usually sinks easily.

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

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

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

A fight ii took place between only two students, the aia_i-th student and bib_i-th student, so aia_i-th student and bib_i-th student are not friends any more.

To meet all these mm 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(2n105,1m105)n,m(2\leq n\leq 10^5,1\leq m\leq 10^5) denoting the number of students and fights.

In the following mm lines, each line contains two integers ai,bi(1ai<bin)a_i,b_i(1\leq a_i<b_i\leq n) denoting the ii-th fight between the aia_i-th students and the bib_i-th student. It is guaranteed that all pairs (ai,bi)(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.