传统题 1000ms 256MiB

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.

福建师范大学第十九届程序设计竞赛重现赛

未参加
状态
已结束
规则
IOI
题目
13
开始于
2022-5-21 6:30
结束于
2023-4-19 14:30
持续时间
8000 小时
主持人
参赛人数
32