#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>#include <math.h>#include <time.h>#include <iostream>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <cctype>#include <stack>#include <string>#include <list>#include <queue>#include <map>#include <vector>#include <deque>#include <set>using namespace std;#ifdef WIN32#define INT64 "%I64d"#define UINT64 "%I64u"#else#define INT64 "%lld"#define UINT64 "%llu"#endif#define INF 0x3f3f3f3f#define eps 1e-8#define PI acos(-1.)#define PI2 asin (1.);typedef long long LL;typedef unsigned int ui;typedef unsigned long long ui64;#define MP make_pairtypedef vector<int> VI;typedef pair<int, int> PII;#define pb push_back#define mp make_pair#define CL(a,b) memset (a, b, sizeof (a))#define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b))#define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c))template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); }template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; }template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; }// aply for the memory of the stack//#pragma comment (linker, "/STACK:1024000000,1024000000")//end#define MAXN 50005#define CY 4 * MAXNint L[CY], R[CY], seg[CY];int n, M;void build(int id, int lt, int rt) {L[id] = lt; R[id] = rt;seg[id] = M + 1;if (lt == rt) return ;int mid = (lt + rt) >> 1;int lc = id << 1, rc = lc + 1;build(lc, lt, mid);build(rc, mid + 1, rt);}void update(int id, int p, int val) {seg[id] = min(seg[id], val);if (L[id] == R[id]) return ;int mid = (L[id] + R[id]) >> 1;int lc = id << 1, rc = lc | 1;if (p <= mid) update(lc, p, val);else update(rc, p, val);}int query(int id, int lt, int rt) {if (L[id] == lt && R[id] == rt) {return seg[id];}int mid = (L[id] + R[id]) >> 1;int lc = id << 1, rc = lc | 1;if (rt <= mid) return query(lc, lt, rt);else if (lt > mid) return query(rc, lt, rt);else {return min(query(lc, lt, mid), query(rc, mid + 1, rt));}}int main(void) {while (2 == scanf("%d%d", &n, &M)) {build(1, 1, n);update(1, 1, 0);int a, b;while (M--) {scanf("%d%d", &a, &b);int value = query(1, a, b - 1);update(1, b, value + 1);}printf("%dn", query(1,n, n));}return 0;}
