CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    n = [int(i) for i in input().split()]
    bridge = []
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(len(reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                reqs = reqs[j:]
                break
    
    print(counter)

main()


# Optimized solution
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()
# Original solution
N, M = list(map(int, input().split()))
E = []
for i in range(M):
    a, b = list(map(int, input().split()))
    a, b = a-1, b-1
    E.append([a, b])

E.sort()
l, r = 0, float('inf')
ans = 0
for a, b in E:
    if b <= l or a >= r:
        ans += 1
        l, r = a, b
    else:
        l = max(a, l)
        r = min(b, r)

print((ans + 1))


# Optimized solution
N, M = list(map(int, input().split()))
E = []
for i in range(M):
    a, b = list(map(int, input().split()))
    a, b = a - 1, b - 1
    E.append([a, b])

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

r = 0
ans = 0
for a, b in E:
    if a >= r:
        ans += 1
        r = b

print(ans)
# Original solution
N, M = list(map(int, input().split()))
Requests = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1])

cut, ans = 0, 0
for l, r in Requests:
    if l >= cut:
        ans += 1
        cut = r

print(ans)


# Optimized solution
N, M = list(map(int, input().split()))
Data = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1])


ans, r = 0, 0
for a, b in Data:
    if a >= r:
        ans += 1
        r = b

print(ans)
# Original solution
n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  array = list(map(int,input().split()))
  ab.append(array)

w = [[int(i) for i in range(ab[u][0],ab[u][1])] for u in range(m)]
ans = 0
#print(w)
import collections
while True:
  d = [e for row in w for e in row]
  #print(d)
  if d == []:
    print(ans)
    break
  else:
    # collections.Counter使用時は宣言する
    c = collections.Counter(d)
    t = c.most_common()[0][0]
    ans += 1
    w = [i for i in w if not t in i]
    #print(w)

# Optimized solution
from operator import itemgetter

n, m = [int(i) for i in input().split()]

# 区間の終端でソート
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0

for a in ab:
    # a が removed より大きい = まだ取り除いてない
    if a[0] > removed:
        #print(a)
        removed = a[1] - 1
        ans += 1

print(ans)
# Original solution
import copy

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

count = 0
while len(reqs) > 0:
    copied_req = copy.deepcopy(reqs)
    _, idx = list(map(min, list(zip(*copied_req))))
    for req in reqs:
        if req[0] < idx:
            copied_req.remove(req)
    count += 1
    reqs = copied_req
print(count)

# Optimized solution
N, M = list(map(int, input().split()))
reqs = []
ans = 0
B = 0
for _ in range(M):
    a, b = list(map(int, input().split()))
    reqs.append((a, b))
reqs = sorted(reqs, key=lambda x: x[1])
for i in range(M):
    a, b = reqs[i]
    if a >= B:
        B = b
        ans += 1
print(ans)
# Original solution
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = list(map(int, open(0).read().split()))
    Q = sorted([(a, b) for a, b in zip(*[iter(AB)] * 2)], key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if not a < cur <= b:
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = list(map(int, open(0).read().split()))
    Q = [(a, b) for a, b in zip(*[iter(AB)] * 2)]
    Q.sort(key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if not a < cur <= b:
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = list(map(int, open(0).read().split()))
    Q = [(a, b) for a, b in zip(*[iter(AB)] * 2)]
    Q.sort(key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if not a < cur <= b:
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = list(map(int, open(0).read().split()))
    Q = [(a, b) for a, b in zip(*[iter(AB)] * 2)]
    Q.sort(key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if a >= cur:  # need to break another bridge
            ans += 1
            cur = b
    print(ans)


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

war = {}
for i in range(M):
    a, b = list(map(int, input().split()))
    if(b in war):
        if(a > war[b]):
            war[b] = a
    else:
        war[b] = a

ans = 1
b_list = list(war.keys())
b_list = sorted(b_list)
r_bridge = b_list[0] - 1

while(True):
    # print(b_list)
    for b in b_list[:]:
        a = war[b]
        if(a <= r_bridge < b):
            b_list.remove(b)

    if(b_list != []):
        r_bridge = b_list[0] - 1
        ans += 1
    else:
        break

print(ans)

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

war = {}
for i in range(M):
    a, b = list(map(int, input().split()))
    if(b in war):
        if(a > war[b]):
            war[b] = a
    else:
        war[b] = a

ans = 1
b_list = list(war.keys())
b_list = sorted(b_list)
r_bridge = b_list[0] - 1

for b in b_list:
    a = war[b]
    if(a <= r_bridge):
        continue
    else:
        r_bridge = b - 1
        ans += 1

print(ans)
# Original solution
from collections import Counter
n,m=list(map(int,input().split()))
r=[]
ac=0
ans=0

def lmax(a):
    c=[]
    for i in a:
        c+=i
    return  Counter(c).most_common()[0][0]

for i in range(m):
    a,b=list(map(int,input().split()))
    l=list(range(a,b))
    r.append(l)
c=0
k=0
while ac!=m:
    mc=lmax(r)
    lr =len(r)
    c=0
    k=0
    while c<lr:
        if mc in r[k]:
            del r[k]
            ac+=1
            c+=1
        else:
            k+=1
            c+=1
    ans+=1
print(ans)    

# Optimized solution
n,m=list(map(int,input().split()))
r=[]
br=[1 for i in range(n)]
c=0
for i in range(m):
    a,b=list(map(int,input().split()))
    r.append([b,a])
r.sort()
for i in range(m):
    if sum(br[r[i][1]:r[i][0]])==r[i][0]-r[i][1]:
        br[r[i][0]-1]=0
        c+=1
print(c)
# Original solution
def sarch(listd, num, i):
    if listd[i - 2] == num:
        return 1
    return 0

N, M = list(map(int, input().split()))
data = []
brige = []
for i in range(M):
    A, B = list(map(int, input().split()))
    data.append(B)
    listdata = [0 for j in range(1, A)]
    for j in range(A, B):
        listdata.append(j)
    listdata.extend([0 for j in range(B, N)])
    brige.append(listdata)


ans = []


keylist = [0 for i in range(M)]

for i in range(1, N + 1):
    for j in range(M):
        if keylist[j] != 1 and sarch(brige[j], i, data[j]) == 1:
            ans.append(i)
            for k in range(M):
                if brige[k][i - 1] == i:
                    keylist[k] = 1
            keylist[j] = 1


print((len(ans)))


# Optimized solution
N, M = list(map(int, input().split()))
AB = []
for i in range(M):
    a, b = list(map(int, input().split()))
    AB.append([b, a])
AB.sort()
for i in range(M):
    if i == 0:
       j = AB[i][0] - 1
       ans = 1
    else:
        if AB[i][1] <= j and j < AB[i][0]:
            1
        else:
            j = AB[i][0] - 1
            ans += 1

print(ans)
# Original solution
n,m = list(map(int,input().split()))

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

cut.sort()

b_min = cut[0][1]
count = 0

for a,b in cut[1:]:
  if b_min > b:
    b_min = b
    continue
  if b_min <= a:
    count += 1
    b_min = b

print((count+1))



# Optimized solution
n,m = list(map(int,input().split()))
cut = []
for _ in range(m):
  a,b = list(map(int,input().split()))
  cut.append((a,b))
cut.sort(key = lambda x:x[1])

ex_b  = cut[0][1]
count = 0
for a,b in cut[1:]:
  if a >= ex_b:
    count += 1
    ex_b = b
print((count+1))
# Original solution
n, m = list(map(int, input().split()))
ab_list = list()
for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append([a, b])
ab_list = sorted(ab_list, key=lambda x: x[1])
n_list = [1 for i in range(n)]
for a, b in ab_list:
    t_list = n_list[a:b]
    v = t_list.count(0)
    if v == 0:
        n_list[b-1] = 0
print((n_list.count(0)))

# Optimized solution
n, m = list(map(int, input().split()))
ab_list = list()
for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append([a, b])
ab_list = sorted(ab_list, key=lambda x: x[1])
x = -1
ans = 0
for a, b in ab_list:
    if a <= x:
        continue
    else:
        x = b-1
        ans += 1
print(ans)
# Original solution
n,m=list(map(int,input().split()))

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

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

#print(l_target)

cut_pos=[]
for target in l_target:
    is_ok=False
    for pos in cut_pos:
        if (target[0]<pos<target[1]):
            is_ok=True
            break
    
    if(not is_ok):
        cut_pos.append(target[1]-0.5)

print((len(cut_pos)))

# Optimized solution
n,m=list(map(int,input().split()))

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

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

count=0
pre_pos=0
for target in l_target:
    if (target[0]<pre_pos<target[1]):
        continue
    
    count+=1
    pre_pos=target[1]-0.5

print(count)
# Original solution
n, m = list(map(int, input().split()))
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
for i in range(m):
    ab[i].sort()
while len(ab) > 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0]
    list.sort(ab, reverse=True)
    remove = ab.index(end)
    if remove >= 1:
        while ab[remove - 1][0] < end[1]:
            remove -= 1
            if remove == 0:
                break
    del ab[(remove):]
    count += 1
print((int(count)))

# Optimized solution
n, m = list(map(int, input().split()))
l = []
for i in range(m):
    a, b = list(map(int, input().split()))
    l.append((b, a))
l.sort()
answer = 0
last = 0
for b, a in l:
    if a >= last:
        answer += 1
        last = b
print(answer)
# Original solution
import sys
input = sys.stdin.readline
def main():
    n, m = list(map(int, input().split()))
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = []
            res.extend(rule[j + 1])
    print(ans)


if __name__ == '__main__':
    main()


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


def main():
    n, m = list(map(int, input().split()))
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = rule[j + 1][:]
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
N,M=list(map(int,input().split()))
conflict=[tuple(map(int,input().split())) for i in range(M)]
conflict.sort(key=lambda x:x[0])
ans=0
Right=N
for i in range(M):
    if conflict[i][0]>=Right:
        Right=conflict[i][1]
        ans+=1
    else:
        Right=min(Right,conflict[i][1])
print((ans+1))

# Optimized solution
N,M=list(map(int,input().split()))
need=[tuple(map(int,input().split())) for i in range(M)]
need.sort(key=lambda x:x[0])
ans=0
bef=0
for a,b in need:
    if a<=bef:
        bef=min(b-1,bef)
    else:
        ans+=1
        bef=b-1
print(ans)
# Original solution
N,M=list(map(int,input().split()))
need=[tuple(map(int,input().split())) for i in range(M)]
need.sort(key=lambda x:x[0])
ans=0
bef=0
for a,b in need:
    if a<=bef:
        bef=min(b-1,bef)
    else:
        ans+=1
        bef=b-1
print(ans)

# Optimized solution
N,M=list(map(int,input().split()))
need=[tuple(map(int,input().split())) for i in range(M)]
ans=0
need.sort(key=lambda x:x[1])
bef=1
for a,b in need:
    if a<bef:
        continue
    else:
        ans+=1
        bef=b
print(ans)
# Original solution
n,m = list(map(int,input().split()))

demands= []

for i in range(m):
    demands.append(list(map(int,input().split())))

demands.sort()

cut = []

for d in demands:
    flag = True
    for c in cut:
        if c[0] < d[1] and c[1] > d[0]:
            flag = False
            c[0] = max(c[0],d[0])
            c[1] = min(c[1],d[1])
            break
    if flag:
        cut.append(d)

print((len(cut)))

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

d.sort(key=lambda x:x[1])
ans=0
c=0
for i in range(M):
    a,b=d[i]
    if a>=c:
        ans+=1
        c=b
print(ans)
# Original solution
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(m)]

x = 0
ans = 0

while x < n:
    p = 10000000
    for y in a:
        if y[0] >= x:
            p = min(p, y[1])
    for y in a:
        if y[0] < x:
            a.remove(y)
    if p <= n:
        ans += 1
    if p == 10000000:
        break
    x = p

print(ans)

# Optimized solution
n, m = list(map(int, input().split()))

l = []

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

l.sort()

ans = 0
x = 0

for i in range(m):
    if l[i][1] >= x:
        ans += 1
        x = l[i][0]

print(ans)
# Original solution
from operator import itemgetter

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

ab = []
for i in range(m):
    a,b = list(map(int, input().split()))
    ab.append([a-1,b-1])

ab.sort(key=itemgetter(1))

fall = [0 for i in range(n-1)]

for i in range(len(ab)):
    flag = True
    for j in range(ab[i][0],ab[i][1]):
        if fall[j]:
            flag = False
            break
    if flag:
        fall[ab[i][1]-1] = 1

print((fall.count(1)))


# Optimized solution
from operator import itemgetter

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

ab = []
for i in range(m):
    a,b = list(map(int, input().split()))
    ab.append([a-1,b-1])

ab.sort(key=itemgetter(1))

fall = -1
ans = 0

for i in range(m):
    if fall < ab[i][0]:
        ans += 1
        fall = ab[i][1]-1

print(ans)
# Original solution
N, M = list(map(int, input().split()))
war_pairs = []
for _ in range(M):
    a, b = list(map(int, input().split()))
    war_pairs.append((a, b))

# 取り除く橋についてbit全探索
bridge_cnt = N - 1
for i in range(2 ** bridge_cnt):

    bridges = [True] * bridge_cnt
    for j in range(bridge_cnt):
        if (i >> j) & 1:
            bridges[bridge_cnt - 1 - j] = False

    # war_pairs間でたどり着けないか確認
    is_unreachable_all = True
    for (a, b) in war_pairs:
        bridges_between_ab = bridges[a - 1:b - 1]
        if all(bridges_between_ab):
            is_unreachable_all = False

    if is_unreachable_all:
        print((bridges.count(False)))
        exit()


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

pairs.sort(key=lambda x: x[1])  # 終端が早い順に並び替え

# 重複区間除去(greedy)
current = 0
bag = []
for pair in pairs:
    if pair[0] >= current:
        bag.append(pair)
        current = pair[1]

print((len(bag)))
# Original solution
N, M = list(map(int, input().split()))
dem = [[0, 0] for i in range(M)]
for i in range(M):
    dem[i][0], dem[i][1] = list(map(int, input().split()))
dem.sort(key=lambda x: (x[1]))
br_flag = [False for i in range(N-1)]
count = 0
for i in range(M):
    for j in range(dem[i][1]-dem[i][0]):
        if br_flag[dem[i][0] - 1 + j]:
            break
        elif j == dem[i][1] - dem[i][0] - 1:
            br_flag[dem[i][1]-2] = True
            count += 1
print(count)


# Optimized solution
N, M = list(map(int, input().split()))
dem = [[0, 0] for i in range(M)]
for i in range(M):
    dem[i][0], dem[i][1] = list(map(int, input().split()))
dem.sort(key=lambda x: (x[1]))
br_flag = [False for i in range(N-1)]
count = 0
a = 0
for i in range(M):
    if a < dem[i][0]:
        br_flag[dem[i][1]-2] = True
        a = dem[i][1] - 1
        count += 1
print(count)
# Original solution
N, M, *A = list(map(int, open(0).read().split()))
*A, = list(zip(*[iter(A)]*2))
A.sort()
cnt = 0
R = 0
for a, b in A:
    if R <= a:
        cnt += 1
        R = b
    elif b < R:
        R = b
print(cnt)


# Optimized solution
N,M,*A=list(map(int,open(0).read().split()));c=0
for a,b in sorted(zip(*[iter(A)]*2))[::-1]:
	if b<=N:c+=1;N=a
print(c)
# Original solution
N, M = [int(t) for t in input().split()]
R = []
for i in range(M):
    a, b = [int(t) for t in input().split()]
    R.append((a, b))

R.sort()

inf = float('inf')
Ra = [inf for a in range(N + 1)]
for a, b in R:
    Ra[a] = min(Ra[a], b)
R = [(a, Ra[a]) for a in range(1, N+1) if Ra[a] != inf]

R.sort(key=lambda r: r[1])

bridge = [True] * (N)

last = None
for a, b in R:
    if last == None or last < a:
        bridge[b-1] = False
        last = b-1
print((sum(1 for b in bridge if not b)))


# Optimized solution
N, M = [int(t) for t in input().split()]
R = []
for i in range(M):
    a, b = [int(t) for t in input().split()]
    R.append((a, b))

R.sort(key=lambda r: r[1])

last  = -1
count = 0
for a, b in R:
    if last < a:
        last = b - 1
        count += 1
print(count)
# Original solution
N, M = [int(t) for t in input().split()]
R = []
for i in range(M):
    a, b = [int(t) for t in input().split()]
    R.append((a, b))

R.sort(key=lambda r: r[1])

last  = -1
count = 0
for a, b in R:
    if last < a:
        last = b - 1
        count += 1
print(count)

# Optimized solution
N, M = [int(t) for t in input().split()]
R = []
for i in range(M):
    a, b = [int(t) for t in input().split()]
    R.append((a, b))

last  = -1  # the last broken bridge
count = 0   # the number of broken bridges
for a, b in sorted(R, key=lambda r: r[1]):
    if last < a:
        last = b - 1
        count += 1
print(count)
# Original solution
n,m=list(map(int,input().split()))
ab=[list(map(int,input().split()))for _ in range(m)]
ab.sort()
l,r=ab[0]
ans=1
for i,j in ab[1:]:
  if j<=l or r<=i:
    ans+=1
    l,r=i,j
  l=max(l,i)
  r=min(r,j)
print(ans)

# Optimized solution
n,m=list(map(int,input().split()))
ab=[list(map(int,input().split()))for _ in range(m)]
ab.sort()
l,r=ab[0]
ans=1
for a,b in ab[1:]:
  if r<=a:
    ans+=1
    l,r=a,b
  else:
    l=max(l,a)
    r=min(r,b)
print(ans)
# Original solution
from pprint import pprint
from copy import deepcopy

#N <= 10**5なので、全探索はNG
#Greedyでいける？


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

requests = [list(map(int,input().split())) for _ in range(m)]

bridge_list = [[] for _ in range(n-1)]

for i in range(m):
    startpoint = requests[i][0]
    endpoint = requests[i][1]
    for j in range(startpoint,endpoint):
        bridge_list[j-1].append(i)

#pprint(bridge_list)

checked_requests = [0] * m

#bridge_list = sorted(bridge_list, key=lambda x: len(x))

counter = 0

while sum(checked_requests) != m:
    #max_index = bridge_list.index(max(list(map(len,bridge_list))))
    length_list = list(map(len,bridge_list))
    max_index = length_list.index(max(length_list))

    #bridge_list[max_index]を直接 for k in に突っ込むと、removeメソッドがあるため動作がおかしくなってしまう。
    temp = deepcopy(bridge_list[max_index])

    for k in temp:
        checked_requests[k] = 1
        for l in range(n-1):
            try:
                bridge_list[l].remove(k)
            except ValueError:
                pass
    
    counter += 1
    
pprint(counter)







# Optimized solution
#この方法だとTLEになるためNG

from pprint import pprint
from copy import deepcopy

#N <= 10**5なので、全探索はNG
#Greedyでいける？


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

requests = [list(map(int,input().split())) for _ in range(m)]

#区間スケジュール問題と考え、終端が小さい順で並べる。その後Greedyで計算。
requests = sorted(requests, key=lambda x:x[1])

counter = 0
before_point = -float('inf')

#pprint(requests)

for i in range(m):
    if requests[i][0] >= before_point:
        counter += 1
        before_point = requests[i][1]
        #print("requests[{}]={} YES".format(i,requests[i]))
    else:
        #print("requests[{}]={} NO".format(i,requests[i]))
        pass

print(counter)
# Original solution
N, M = list(map(int, input().split()))

AB = [list(map(int, input().split())) for _ in range(M)]

AB.sort(key = lambda x: x[0])

MAX = 10 ** 9

count = 1
min_ = MAX
for a, b in AB:
    if a < min_:
        min_ = min(min_, b)
    else:
        count += 1
        min_ = b

print (count)


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

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

count = 1
B = 10 ** 9
for a, b in AB:
    if a < B:
        B = min(B, b)
    else:
        count += 1
        B = b

print (count)
# Original solution
N, M = list(map(int, input().split()))

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

count = 1
B = 10 ** 9
for a, b in AB:
    if a < B:
        B = min(B, b)
    else:
        count += 1
        B = b

print (count)


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

AB = [tuple(map(int, input().split())) for _ in range(M)]

AB.sort(key = lambda x: x[1]) #右側が小さい順にソート
AB.sort(key = lambda x: x[0]) #左側が小さい順にソート

ans = 0

right = N + 1
for a, b in AB:
    if a < right:
        right = min(right, b)
    else:
        ans += 1
        right = b

print((ans + 1))
# Original solution
from operator import itemgetter

n, m = [int(i) for i in input().split()]
A, B = list(zip(*[[int(i) for i in input().split()] for j in range(m)]))

A, B = list(zip(*sorted(zip(A, B), key=itemgetter(1, 0))))

last = -1
ans = 0

for a, b in zip(A, B):
    if last <= a:
        ans += 1
        last = b

print(ans)

# Optimized solution
n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(m)]

A.sort(key=lambda a:a[1])
ans = 0
i = 0

while i < m:
    b = A[i][1]
    ans += 1
    i += 1
    while i < m:
        if A[i][0] >= b:
            break
        i += 1

print(ans)
# Original solution
N,M = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 1
l = L[0][0]
r = L[0][1]
for a,b in L:
    if r <= a or l >= b:
        ans += 1
        l = a
        r = b
    else:
        l = a
        r = min(r,b)
print(ans)


# Optimized solution
N,M = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 1
l = L[0][0]
r = L[0][1]
for a,b in L:
    if r <= a:
        ans += 1
        l = a
        r = b
    else:
        l = a
        r = min(r,b)
print(ans)