CodeEff/ECCO huggingface dataset:
# Original solution
def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def main():
    num_nodes, num_regions = tuple(input_ints())
    regions = [tuple(input_ints()) for _ in range(num_regions)]

    nodes = set()
    for r in regions:
        nodes.add(r[0])
        nodes.add(r[1])

    regions.sort(key=lambda x: (x[1] - x[0], x[0]))

    i = 0
    while i < len(regions):
        regions[0:i+1] + [r for r in regions[i+1:] if not (regions[i][0] <= r[0] and r[1] <= regions[i][1])]
        i += 1

    def solve(rs, steps):
        min_steps = 99999999999

        for i in [i for i in range(rs[0][0], rs[0][1]) if i in nodes]:
            rs2 = [r for r in rs if not r[0] <= i < r[1]]
            if rs2:
                min_steps = min(solve(rs2, steps + 1), min_steps)
            else:
                return steps

        return min_steps

    print(solve(regions, 1))


main()


# Optimized solution
def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def main():
    num_nodes, num_regions = tuple(input_ints())
    regions = [tuple(input_ints()) for _ in range(num_regions)]
    regions.sort(key=lambda r: r[1])

    edges = []
    for r in regions:
        if not edges or edges[-1] < r[0]:
            edges.append(r[1] - 1)

    print(len(edges))


main()
# Original solution
# ABC103D
# 貪欲法：区間スケジューリング問題に帰着
# ソートして喧嘩している遠い島(b[i])の最も近いところから貪欲に選んでいく
# ex) 1-10, 2-5, 6-8
# なら2-5, 6-8を選ぶ．
N, M = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
##print(ab)
ans = 1             # 一つ目分
tmp = ab[0][1] - 0.1      # 一つ目の橋は必ず壊すので
for i in range(1, M):
    if ab[i][0] < tmp < ab[i][1]:   # 直近で壊した橋が喧嘩している島の間にある時は何もしない
        pass
    else:                           # 間にない時は新しく橋を壊す
        ans += 1
        tmp = ab[i][1] - 0.1

print(ans)

# Optimized solution
N, M = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
ans = 1
tmp = ab[0][1]
for i in range(1, M):
    if tmp <= ab[i][0]:
        ans += 1
        tmp = ab[i][1]
print(ans)
# Original solution
import sys
from collections import defaultdict
input = sys.stdin.readline


n, m = list(map(int, input().split()))
path = defaultdict(list)

for _ in range(m):
    a, b = list(map(int, input().split()))
    path[a].append(b)

idx = 1
ans = 1
right = n
while idx <= n:
    candidate = path[idx]
    if not candidate:
        idx += 1
        continue
    if right <= idx:
        ans += 1
        right = n
    cut = min(candidate)
    right = min(right, cut)
    idx += 1

print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
INF = float('INF')

n, m = list(map(int, input().split()))
path = [INF]*(n+1)

for _ in range(m):
    a, b = list(map(int, input().split()))
    path[a] = min(path[a], b)

left = 1
ans = 1
right = n
while left <= n:
    cut = path[left]
    if cut == INF:
        left += 1
        continue
    if right <= left:
        ans += 1
        right = n
    right = min(right, cut)
    left += 1

print(ans)
# Original solution
N, M = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(M)]

cnt = 0
while len(AB) > 0:
    bridges = [0] * (N - 1)
    for a, b in AB:
        for i in range(a - 1, b - 1):
            bridges[i] += 1
    collapse = bridges.index(max(bridges))
    cnt += 1
    AB = list([ab for ab in AB if ab[0] > collapse + 1 or collapse + 1 >= ab[1]])
print(cnt)

# Optimized solution
N, M = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(M)]

AB.sort(key=lambda ab: ab[1])
removed = list()
for a, b in AB:
    if len(removed) == 0:
        removed.append(b - 1)
    elif a <= removed[-1] < b:
        continue
    else:
        removed.append(b - 1)
print((len(removed)))
# Original solution
#!/usr/bin/env python3

from collections import defaultdict

def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    atoi = defaultdict(list)
    btoi = defaultdict(list)
    for i in range(m):
        aa, bb = list(map(int, input().split()))
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  # Already achieved
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3

import sys
from collections import defaultdict

def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    atoi = defaultdict(list)
    btoi = defaultdict(list)
    for i in range(m):
        aa, bb = list(map(int, sys.stdin.readline().split()))
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  # Already achieved
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()
# Original solution
#!/usr/bin/env python3

import sys
from collections import defaultdict

def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    atoi = defaultdict(list)
    btoi = defaultdict(list)
    for i in range(m):
        aa, bb = list(map(int, sys.stdin.readline().split()))
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  # Already achieved
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3

import sys

def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    atoi = [[] for i in range(n)]
    btoi = [[] for i in range(n)]
    for i in range(m):
        aa, bb = list(map(int, sys.stdin.readline().split()))
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  # Already achieved
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()
# Original solution
N, M = list(map(int, input().split()))
requests = [tuple(map(int, input().split())) for _ in range(M)]
requests.sort(key=lambda x: x[1])
connects = [1] * N
for a, b in requests:
    if all(connects[a:b]):
        connects[b-1] = 0
print((connects.count(0)))

# Optimized solution
N, M = list(map(int, input().split()))
requests = [tuple(map(int, input().split())) for _ in range(M)]
requests.sort(key=lambda x: x[1])
counts = 0
left = 0
for a, b in requests:
    if a >= left:
        left = b
        counts += 1
print(counts)
# Original solution
from heapq import heappush, heappop

N, M = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(M)]
LR.sort(key=lambda a: (a[0], -a[0]))

R = 10**18
ans = 0
for l, r in LR:
    if R <= l:
        ans += 1
        R = 10**18
    R = min(R, r)

print((ans + 1))


# Optimized solution
N, M = list(map(int, input().split()))

AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key=lambda a: (a[0], -a[1]))

ans = 1
right = 10**18
for l, r in AB:
    if l >= right:
        ans += 1
        right = 10**18
    right = min(right, r)
print(ans)
# Original solution
N, M = list(map(int, input().split()))

AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key=lambda a: (a[0], -a[1]))

ans = 1
right = 10**18
for l, r in AB:
    if l >= right:
        ans += 1
        right = 10**18
    right = min(right, r)
print(ans)

# Optimized solution
N, M = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(M)]

AB.sort(key=lambda a: (a[1], a[0]))

mx = 10**18
ans = 0
for a, b in AB:
    if a >= mx:
        ans += 1
        mx = 10**18
    mx = min(mx, b)
print((ans + 1))
# Original solution
N, M = list(map(int,input().split()))

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))

banned_list = sorted(banned_list,key=lambda x:x[1])
status = [1 for _ in range(N-1)]
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if not 0 in status[a-1:b-1]:
        counter += 1
        status[b-2] = 0
print(counter)

# Optimized solution
N, M = list(map(int,input().split()))

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
banned_list = sorted(banned_list,key=lambda x:x[1])
#status = [1 for _ in range(N-1)]
status = set()
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if len([one for one in status if (one >= a-1 and one < b-1)]) == 0:
        status  |= {b-2}
        counter += 1
print(counter)
# Original solution
def main():
    N, M = list(map(int, input().split()))
    a_b = sorted([list(map(int, input().split())) for _ in range(M)])
    used = [0] * M
    ans = 0
    for i in range(M):
        k = M - i - 1
        if used[k]:
            continue
        used[k], c = 1, a_b[k][0]
        for j in range(k):
            if a_b[j][0] <= c < a_b[j][1]:
                used[j] = 1
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()


# Optimized solution
import sys
input = sys.stdin.readline

def main():
    N, M = list(map(int, input().split()))
    a_b = sorted([list(map(int, input().split())) for _ in range(M)])
    used = [0] * M
    ans = 0
    for i in range(M):
        k = M - i - 1
        if used[k]:
            continue
        used[k], c = 1, a_b[k][0]
        for j in range(k):
            if a_b[j][0] <= c < a_b[j][1]:
                used[j] = 1
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()
# Original solution
N, M = list(map(int, input().split()))

bridges = []
for i in range(M):
	bridges.append(list(map(int, input().split())))

intervals = sorted(bridges, key=lambda x: (x[1], x[0]))

#print(bridges)
count=1
done=[intervals[0]]

for interval in intervals:
	#print(interval)
	if not interval[0] < done[-1][1]:
		count += 1
		done.append(interval)	
#print(done)
print(count) 

# Optimized solution
N, M = list(map(int, input().split()))

bridges = []
for i in range(M):
	bridges.append(list(map(int, input().split())))

intervals = sorted(bridges, key=lambda x: x[1])

#print(bridges)
count=1
done=[intervals[0]]

for interval in intervals:
	#print(interval)
    # we cut the last bridage of last processed interval
	if not interval[0] < done[-1][1]:
		count += 1
		done.append(interval)	
#print(done)
print(count)
# Original solution
N,M = list(map(int,input().split(' ')))
sections_a = []
sections_b = []

for _ in range(M):
    a,b = list(map(int,input().split(' ')))
    sections_a.append(a)
    sections_b.append(b)

tmp_a = [sections_a[0]]
tmp_b = [sections_b[0]]
for i in range(1,len(sections_a)):
    for j in range(i):
        if sections_a[i] < tmp_a[j]:
            tmp_a.insert(j,sections_a[i])
            tmp_b.insert(j,sections_b[i])
            break
        if j == i -1:
            tmp_a.append(sections_a[i])
            tmp_b.append(sections_b[i])
min_end = 10000000000000000
sorted_list_a = tmp_a
sorted_list_b = tmp_b
cnt = 0
for i in range(len(sorted_list_a)):
    if min_end <= sorted_list_a[i]:
        cnt += 1
        min_end = 10000000000000000
    min_end = min(min_end,sorted_list_b[i])
cnt += 1
print(cnt)

# Optimized solution
N,M = list(map(int,input().split(' ')))
sections = [list(map(int,input().split(' '))) for _ in range(M) ]

'''
tmp_list = [sections[0]]
for i in range(1,len(sections)):
    for j in range(i):
        if sections[i] < tmp_list[j]:
            tmp_list.insert(j,sections[i])
            break
        if j == i -1:
            tmp_list.append(sections[i])
'''
min_end = 10000000000000000
sorted_list = sorted(sections)
cnt = 0
for section in sorted_list:
    if min_end <= section[0]:
        cnt += 1
        min_end = min_end = 10000000000000000
    min_end = min(min_end,section[1])
cnt += 1
print(cnt)
# Original solution
a,b = list(map(int,input().split()))

input_lines = [list(map(int,input().split())) for i in range(b)]
input_lines = sorted(input_lines,key=lambda x: x[1]) #各要素において[1]に基づきソートする

c=[0]
for i in input_lines:
    p=0
    for j in c:
        if j > i[0]:
            p=1
    if p==0:
        c.append(i[1])
        
print((len(c)-1))




# Optimized solution
a,b = list(map(int,input().split()))

input_lines = [list(map(int,input().split())) for i in range(b)]
input_lines = sorted(input_lines,key=lambda x: x[1]) #各要素において[1]に基づきソートする

c=[0]
for i in input_lines:
    #for j in c:
    #   if j > i[0]:
    #        p=1
    if max(c)<=i[0]:
        c.append(i[1])
        
print((len(c)-1))
# Original solution
N, M = list(map(int, input().split()))
_input = []
for i in range(M):
    _input.append(list(map(int,input().split())))

_input.sort(key=lambda x: x[1])

removed = []

for a,b in _input:
    flag = False
    for i in removed:
        if a <= i < b:
            flag = True
    if not flag:
        removed.append(b-1)

print((len(removed)))

# Optimized solution
N, M = list(map(int, input().split()))
_input = []
for i in range(M):
    _input.append(list(map(int,input().split())))

_input.sort(key=lambda x: x[1])

removed = []

for a,b in _input:
    flag = False
    for i in removed:
        if a <= i < b:
            flag = True
            break
    if not flag:
        removed.append(b-1)

print((len(removed)))
# Original solution
n,m = list(map(int,input().split()))
youbou = [list(map(int,input().split())) for i in range(m)]
youbou.sort(key = lambda x: x[1])
ans,prev = 0,-1
for p in youbou:
	if prev < p[0]:
		prev = p[1] - 1
		ans += 1
print(ans)

# Optimized solution
n,m = list(map(int,input().split()))
youbou = [list(map(int,input().split())) for i in range(m)]
youbou.sort(key = lambda x: x[1])
ans,prev = 0,-1
for i in range(m):
	if prev < youbou[i][0]:
		prev = youbou[i][1] - 1
		ans += 1
print(ans)
# Original solution
N,M=list(map(int,input().split()))
request=[]
for _ in range(M):
    request.append(list(map(int,input().split())))
request.sort(key=lambda x: x[0])
    
memory=request[0][1]
head = request[0][0]
index = 0
ans = 0

def equal():
    if index == M-1: return False
    else: return head == request[index+1][0]

while head <= N:
    if head == memory:
        ans +=1
        memory = N+1
    elif equal():
        index +=1
        memory=min(request[index][1],memory)
    else: head +=1
        
print(ans)

# Optimized solution
N,M=list(map(int,input().split()))
AB=[]
for _ in range(M):
    AB.append(tuple(map(int,input().split())))
    
request_max=0
request_num=0

AB.sort(key=lambda x:x[1])
for (a,b) in AB:
    if a>=request_max:
        request_num +=1
        request_max = b
print(request_num)
# Original solution
import sys
input = sys.stdin.readline
n,m=list(map(int,input().split()))
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=list(map(int,input().split()))

l=sorted(l)

ans=1
for _ in range(n-1):
    for i in l[1:]:
        if i[1]<l[0][0]:
            l.remove(i)
    l.remove(l[0])
    if len(l)!=0:
        ans+=1
    else:
        break

print(ans)


# Optimized solution
import sys
input = sys.stdin.readline
n,m=list(map(int,input().split()))
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=list(map(int,input().split()))

l=sorted(l)

ans=1

c=l[0][0]
for i in range(m):
    if l[i][1]>=c:
        ans+=1
        c=l[i][0]
    else:
        continue
print(ans)
# Original solution
N,M=list(map(int,input().split()))
bridges = [1]*N
islandswar = [[] for _ in range(N+1)]
for i in range(M):
    a,b = list(map(int,input().split()))
    islandswar[b].append(a)
count = 0

def check(a,b):
    for i in range(a,b):
        if bridges[i] == 0:
            return False
    return True
    

for i in range(2,N+1):
    for j in range(0,len(islandswar[i])):
        if check(islandswar[i][j],i):
            bridges[i-1] = 0
            count += 1

print(count)

# Optimized solution
N,M=list(map(int,input().split()))
bridges = [1]*N
islandswar = [[] for _ in range(N+1)]
for i in range(M):
    a,b = list(map(int,input().split()))
    islandswar[b].append(a)
count = 0
currightest = 0

def check(a,b):
    for i in range(a,b):
        if bridges[i] == 0:
            return False
    return True
    

for i in range(2,N+1):
    for j in range(0,len(islandswar[i])):
        if islandswar[i][j] >= currightest:
            if check(islandswar[i][j],i):
                bridges[i-1] = 0
                currightest = i
                count += 1

print(count)
# Original solution
#!/usr/bin/env python3
import sys
import operator


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    AB = list(zip(a,b))
    AB.sort(key=operator.itemgetter(1))

    db = []
    for a,b in AB:
        bAppend = True
        for i in range(a,b):
            if i in db:
                bAppend = False
                break
        if bAppend:
            db.append(b-1)

    print((len(db)))


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
import operator


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    AB = list(zip(a,b))
    AB.sort(key=operator.itemgetter(1))

    db = []
    for a,b in AB:
        bAppend = True
        for di in db:
            if a <= di < b:
                bAppend = False
                break
        if bAppend:
            db.append(b-1)

    print((len(db)))


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()
# Original solution
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(eval(input()))
def MI(): return list(map(int,input().split()))
def MF(): return list(map(float,input().split()))
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')


#import numpy as np

def main():
	n,m=MI()
	li=[LI() for _ in range(m)]
	#print(li)
	li.sort(key=lambda x:x[1])
	#print(li)
	
	now=0
	ans=0
	
	for a,b in li:
		if now<=a:
			ans+=1
			now=b
	
	print(ans)
	
	

if __name__ == "__main__":
	main()


# Optimized solution
import sys
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(eval(input()))
def MI(): return list(map(int,input().split()))
def MF(): return list(map(float,input().split()))
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,m=MI()
	li=[LI() for _ in range(m)]

	li.sort(key=lambda x:x[1])
	#print(li)

	now=0
	ans=0

	for a,b in li:
		if now<=a:
			now=b
			ans+=1
	print(ans)

























if __name__ == "__main__":
	main()
# Original solution
import sys
input = sys.stdin.readline

def main():
    N, M = list(map(int, input().split()))
    ab = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x:x[1])

    B = 0
    ans = 0
    for i in range(M):
        a, b = ab[i]
        if a >= B:
            B = b
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()


# Optimized solution
import sys
input = sys.stdin.readline

def main():
    N, M = list(map(int, input().split()))
    ab = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1])
    
    ans = 0
    pre = -1
    for a, b in ab:
        if a >= pre:
            ans += 1
            pre = b
    print(ans)

if __name__ == "__main__":
    main()
# Original solution
n, m = list(map(int, input().split()))
ab = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])

remove = ab[0][1]
res = 1
for i in range(m):
    if remove <= ab[i][0]:
        res += 1
        remove = ab[i][1]

print(res)

# Optimized solution
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x:x[1])

    res = 0
    remove = -1
    for a, b in AB:
        if remove <= a:
            res += 1
            remove = b
    print(res)


if __name__ == '__main__':
    resolve()
# Original solution
break_offs = set()
N, M = list(map(int, input().split()))
for i in range(M):
    a, b = list(map(int, input().split()))
    if a > b:
        a, b = b, a
    break_offs.add((a, b))

covered = []
break_offs = sorted(list(break_offs), key=lambda x:x[1])
for a, b in break_offs:
    found = False
    for area in covered:
        if not (area[0] >= b or area[1] <= a):
            covered.remove(area)
            covered.append((max(area[0], a), min(area[1], b)))
            found = True
            break

    if not found:
        covered.append((a, b))


answer = len(covered)
print(answer)

# Optimized solution
break_offs = set()
N, M = list(map(int, input().split()))
for i in range(M):
    a, b = list(map(int, input().split()))
    if a > b:
        a, b = b, a
    break_offs.add((a, b))

last_bridge = 0
count = 0
for a, b in sorted(list(break_offs), key=lambda x:x[1]):
    if last_bridge <= a:
        last_bridge = b
        count += 1

print(count)