Problem:
 Score : 400 points    Problem Statement There are N islands lining up from west to east, connected by N-1 bridges.  The i -th bridge connects the i -th island from the west and the (i+1) -th island from the west.  One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:  Request i : A dispute took place between the a_i -th island from the west and the b_i -th island from the west. Please make traveling between these islands with bridges impossible.  You decided to remove some bridges to meet all these M requests.  Find the minimum number of bridges that must be removed.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq a_i < b_i \leq N  All pairs (a_i, b_i) are distinct.         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the minimum number of bridges that must be removed.        Sample Input 1 5 2
1 4
2 5      Sample Output 1 1  The requests can be met by removing the bridge connecting the second and third islands from the west.       Sample Input 2 9 5
1 8
2 7
3 5
4 6
7 9      Sample Output 2 2       Sample Input 3 5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5      Sample Output 3 4

Solution (Python):
from operator import itemgetter

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

b = sorted(a, key=itemgetter(1))

removed = -1
ans = 0

for i in range(m):
  if b[i][0] > removed:
    removed = b[i][1] - 1
    ans += 1
    
print(ans)

Solution (Python):
N,M = map(int,input().split())
lis = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    lis[a].append(i+1)
    lis[b].append(-(i+1))
for i in range(N):
    lis[i].sort()

ans = 0
d = set()
for i in range(N):
    for j in range(len(lis[i])):
        if lis[i][j] < 0:
            if -lis[i][j] in d:
                d = set()
                ans += 1
        else:
            d.add(lis[i][j])
print(ans)

Solution (Python):
n,m = map(int,input().split())
l = sorted(list( list(map(int,input().split())) for _ in range(m)), key=lambda x: x[1])
br = -1
ans = 0
for i in l:
    head, tail = i[0], i[1]
    if head < br:
        continue
    else:
        br = tail
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(M)]
data = sorted(data, key=lambda x: x[1])

count = 1
left = data[0][1]
for i in range(1, M):
    if data[i][0] < left:
        left = max(data[i][0], left)
    else:
        count += 1
        left = data[i][1]
print(count)

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, m = ns()
    d = []
    for _ in range(m):
        a, b = ns()
        d.append([a - 1, b - 1])

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

    down = -1
    ans = 0
    for a, b in d:
        if down < a:
            down = b-1
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, m = ns()
    d = []
    for _ in range(m):
        a, b = ns()
        d.append([a - 1, b - 1])

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

    down = []

    for a, b in d:
        idx = bisect.bisect_left(down, a)
        if idx == len(down):
            down.append(b - 1)
    print(len(down))


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
N, M, *AB = [int(_) for _ in open(0).read().split()]
AB = sorted(zip(AB[::2], AB[1::2]))
l, r = AB[0]
ans = 1
for a, b in AB[1:]:
    if r <= a:
        l, r = a, b
        ans += 1
    else:
        r = min(r, b)
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1 ;b-=1
    A.append([a,b])

A=sorted(A, key=lambda x:x[1])
ans=0
last=-5000
for l in A:
    
    if last<l[0]:
        ans+=1
        last=l[1]-1
print(ans)

Solution (Python):
from operator import itemgetter

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


ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))

removed = -1
ans = 0

for a, b in ab:
    
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
itv=[]
for i in range(m):
  a,b=map(int,input().split())
  itv+=[(b,a)]
itv=sorted(itv)
cnt=0
l=1
for t,s in itv:
  if l<=s:
    l=t
    cnt+=1
print(cnt)

Solution (Python):
from sys import maxsize
N, M = map(int, input().split())
bridges = []
for i in range(M):
    a, b = map(int, input().split())
    bridges.append((a, b))

res = 0
end = -maxsize

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

for bridge in bridges:
    if end <= bridge[0]:
        res += 1
        end = bridge[1]
print(res)

Solution (Python):

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

a_b_pairs = [list(map(int, input().split(' '))) for _ in range(M)]
a_b_pairs.sort(key=lambda x: x[1])
right = a_b_pairs[0][1] - 1

ans = 1
for a, b in a_b_pairs[1:]:
    if a > right:
        right = b - 1
        ans += 1

print(ans)

Solution (Python):
n,r=(int(i)-1 for i in input().strip().split(" "))
ar=[]
for _ in range(r+1):
    a,b=(int(i)-1 for i in input().strip().split(" "))
    ar.append((min(a,b),max(a,b)))

ar.sort()
count=1
cur=ar[0]
for i in range(1,len(ar)):
    if ar[i][0]<cur[1]:
        t=(ar[i][0],min(ar[i][1],cur[1]))
        cur=t
    else:
        count+=1
        cur=ar[i]
print(count)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab,key=lambda x:x[1])
res=[]
res.append(ab[0][1]-1)
for i in range(1,m):
    a,b=ab[i]
    if a>res[-1]:
        res.append(b-1)
print(len(res))

Solution (Python):


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



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

ab.sort()

ans = 0
div = -1, -1
for i in range(len(ab)):
    a, b = ab[i]
    

    if a == div[0]:
        continue
    elif a >= div[1]:
        div = a, b
        ans += 1
    else:
        div = a, min(b, div[1])
    

print(ans)

Solution (Python):
n, m = map(int, input().split())

bridge = [None]*m
for i in range(m):
  a, b = map(int, input().split())
  bridge[i] = [b, a]

ans = 0
bridge.sort()

sub = -1
ans = 0
for v in bridge:
  b, a = v[0], v[1]
  if a >= sub:
    sub = b
    ans += 1

print(ans)

Solution (Python):

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

I = [10**10 for _ in range(N)]
for _ in range(M):
  a, b = map(int,input().split())
  I[a-1] = min(b-1,I[a-1])

i = 0
anti = 10**20
ans = 0
for i in range(N):
  if anti == i:
    ans += 1
    anti = 10**10
  anti = min(anti, I[i])
  
print(ans)

Solution (Python):
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
lst.sort(key=lambda x:x[1])
ans=1
pin=lst[0][1]-1

for i in range(1,m):
  if lst[i][0]>pin:
    ans+=1
    pin=lst[i][1]-1

print(ans)

Solution (Python):
N,M=map(int,input().split())
L=list()
for i in range(M):
  a,b=map(int,input().split())
  A=list([b,a])
  L.append(A)
L=sorted(L)
R=[L[0][0]-1]
for j in range(M):
  if R[-1] not in range(L[j][1],L[j][0]):
    R.append(L[j][0]-1)
print(len(R))

Solution (Python):
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]

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

res = 0
pos = 0
for a, b in l:
    if (a - pos) * (b - pos) > 0:
        res += 1
        pos = b - 0.5

print(res)

Solution (Python):
(N,M),*ab = [tuple(map(int, s.split())) for s in open(0)]

ab.sort()

max_a = 0
min_b = float('inf')

ans = 1
for i, (a, b) in enumerate(ab):
    if min_b <= a:
        ans += 1
        max_a, min_b = a, b
    else:
        max_a = max(max_a, a)
        min_b = min(min_b, b)

print(ans)

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

bridges = [0 for i in range(N)]
l = [0]*M

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

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

current_bridge = l[0]
ans = 1

for relations in l:

    if current_bridge[1] > relations[0]:
        continue

    ans += 1
    current_bridge = relations

print(ans)

Solution (Python):
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
ans = 0
pos = 0
for i in range(M):
  if pos<ab[i][0]:
    ans+=1
    pos=ab[i][1]-1
print(ans)

Solution (Python):
x=c=0
for b,a in sorted([[*map(int,t.split())][::-1]for t in open(0)][1:]):
 if a>x:x=b-1;c+=1
print(c)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

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

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

Solution (Python):
N, M = map(int, input().split())
T = []
for i in range(M):
    a, b = map(int, input().split())
    T.append([a, b])

T.sort()
c = 1
s = 1
e = 10**9
for i in range(M):
    a = T[i][0]
    b = T[i][1]
    if a >= e and b > e:
        c += 1
        s = a
        e = b
    elif a > s and b < e:
        s = a
        e = b
    elif a > s:
        s = a
    elif b < e:
        e = b
    else:
        pass
print(c)

Solution (Python):
import bisect
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    
    L,R,_L = [],[],[]
    for i in range(M):
        a,b=mi()
        L.append((a,i))
        R.append((b,i))
        _L.append(a)

    L.sort()
    R.sort()
    _L.sort()

    heapq.heapify(L)    
    heapq.heapify(R)

    l_e = 0
    ans = 0
    seen = set()
    while R:
        r,j = heapq.heappop(R)
        if j in seen: continue

        li = bisect.bisect_left(_L,r)
        if li > 0: li -= 1

        for i in range(l_e,li+1):
            seen.add(L[i][1])

        l_e = li
        ans += 1

    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    
    L,R,_L = [],[],[]
    for i in range(M):
        a,b=mi()
        L.append((a,i))
        R.append((b,i))
        _L.append(a)

    L.sort()
    R.sort()
    _L.sort()

    heapq.heapify(L)    
    heapq.heapify(R)

    
    l_e = 0
    ans = 0
    seen = set()
    while R:
        
        r,j = heapq.heappop(R)
        if j in seen: continue

        li = bisect.bisect_left(_L,r)
        
        if li > 0:
            li -= 1
        
        
        
        

        
        for i in range(l_e,li+1):
            seen.add(L[i][1])

        l_e = li
        ans += 1

    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

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

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

p = 0
t = 0

while len(bridges) > 0:
    t = bridges[0][1]
    p += 1
    bridges = [i for i in bridges if i[0] >= t]

print(p)

Solution (Python):
x=c=0
for a,b in sorted([list(map(int,o.split()))for o in open(0)][1:],key=lambda p:p[1]):
 if a>x:x=b-1;c+=1
print(c)

Solution (Python):
(n, m), *l = [list(map(int, o.split())) for o in open(0)]
x = c = 0
for a, b in sorted(l, key = lambda p:p[1]):
  if a > x:
    x = b - 1
    c += 1
print(c)

Solution (Python):
n, m = map(int, input().split())
x = [-1] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    x[b] = max(x[b], a)
ans = 0
bmx = 0
for i in range(n+1):
    if bmx <= x[i]:
        ans += 1
        bmx = i
print(ans)

Solution (Python):
n, m = map(int, input().split())
events = []
for i in range(m):
    a, b = map(int, input().split())
    events.append((a, 0, i))
    events.append((b-1, 1, i))
events.sort()
solved = [False] * m
todo = []
ans = 0
for i, etype, req in events:
    if etype == 0:
        todo.append(req)
    else:
        if not solved[req]:
            ans += 1
            for req_id in todo:
                solved[req_id] = True
            todo = []
print(ans)

Solution (Python):
n, m = map(int, input().split())
events = []
for i in range(m):
    a, b = map(int, input().split())
    events.append((a, 0, i))
    events.append((b-1, 1, i))
events.sort()
solved = [False] * m
todo = []
ans = 0
for i, etype, req in events:
    if etype == 0:
        todo.append(req)
    else:
        if not solved[req]:
            ans += 1
            for req_id in todo:
                solved[req_id] = True
print(ans)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
R=[]
for i in range (m) :
    a,b=map(int,input().split())
    R.append ([b, a])
R.sort()

def solve() :
    ans,t=0,0
    for i in range (m) :
        if t<=R[i][1]:
            ans+=1
            t=R[i][0]
    return ans
print (solve ())

Solution (Python):
n,m = map(int, raw_input().split())
s,c = [map(int, raw_input().split()) for _ in range(m)], 1
s.sort()
cur = s[0]
for u,v in s[1:]:
	if cur[1] <= u:
		cur,c = [u,v], c + 1 
	else: cur = [max(u, cur[0]),min(v, cur[1])]
print c

Solution (Python):
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
c = 0
s.sort()
cur = []
for u,v in s:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur = [max(u, cur[0]),min(v, cur[1])]
print c + (1 if cur else 0)
"""
---- ------
     4    9
       ---
       5 6
       ------?
       5 

       5 ----- 10
"""

Solution (Python):
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
c = 0
s.sort()
cur = []
for u,v in s:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur = [max(u, cur[0]),min(v, cur[1])]
		if cur[1] - cur[0] == 0: 
			c +=1
			cur = []
print c + (1 if cur else 0)
"""
---- ------
     4    9
       ---
       5 6
       ------?
       5 

       5 ----- 10
"""

Solution (Python):
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
c = 0
s.sort()
cur = s[0]
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
		if cur[1] - cur[0] == 0: 
			c +=1
			cur = []
print c + (1 if cur else 0)


"""
---- ------
     4    9
       ---
       5 6
       ------?
       5 

       5 ----- 10
"""

Solution (Python):
n,m=map(int, input().split())
ab=[list(map(int,input().split()))  for i in  range(m)]

ab=sorted(ab, key=lambda x:(x[0],x[1]), reverse=True)

now=10**5+1

preb=-1
ans=0
for i in range(m):
  if ab[i][1]==preb:
    continue
  if ab[i][1]<=now:
    now=ab[i][0]
    preb=ab[i][1]
    ans+=1
    
print(ans)

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ab.sort(key=itemgetter(1))
ans = [0]
for a, b in ab:
    if ans[-1] < a:
        ans.append(b-1)
print(len(ans) - 1)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
war=[]
for i in range(m):
    start,end=map(int,input().split())
    war.append([start,end])
war=sorted(war,key=lambda x:x[1])
end=0
ans=0
for i in war:
    if i[0]>=end:
        ans+=1
        end=i[1]
print(ans)

Solution (Python):
N,M=map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]

ans = 0
ab.sort(key=lambda x:x[1])

recent_cut = -1
for i in range(M):
    if recent_cut < ab[i][0]:
        recent_cut = ab[i][1]-1
        ans+=1
print(ans)

Solution (Python):
n,m = map(int, input().split())
t = [[n] for i in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  t[a-1].append(b-1)
g = []
for i in t:
  g.append(min(i))
k = 0
ans=0
while k <=n-1:
  e = min(g[k:])
  if e==n:
    break
  ans+=1
  k = e
print(ans)

Solution (Python):
n,m = map(int, input().split())
t = [[n] for i in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  t[a-1].append(b-1)
g = []
for i in t:
  g.append(min(i))
k = 0
ans=0
while k <=n-1:
  e = min(g[k:])
  if e==n:
    break
  ans+=1
  k = e
print(ans)

Solution (Python):
n,m = map(int, input().split())
t = [[n] for i in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  t[a-1].append(b-1)
g = []
for i in t:
  g.append(sorted(i))
k = 0
ans=0
while k <=n-1:
  e = n
  for i in g[k:]:
    e = min(e,i[0])
  if e==n:
    break
  ans+=1
  k = e
print(ans)

Solution (Python):
n,m = map(int, input().split())
g = [[n] for i in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  g[a-1].append(b-1)
k = 0
ans=0
while k <=n-1:
  e = n
  for i in g[k:]:
    e = min(e,min(i))
  if e==n:
    break
  ans+=1
  k = e
print(ans)

Solution (Python):
N, M = map(int, input().split())
B = [tuple(map(int, input().split())) for _ in range(M)]
B.sort()
r = 0
res = 0
for a, b in B:
    if a >= r:
        res += 1
        r = b
    else:
        r = min(r, b)
print(res)

Solution (Python):
def solve():
    N,M = map(int,input().split())
    hostile = []
    for _ in range(M):
        a, b = map(int,input().split())
        hostile.append((a,b))
    
    hostile.sort(key=lambda x:x[1])
    ans = 0
    last_cut = -1
    for a,b in hostile:
        if last_cut < a:
            last_cut = b-1
            ans += 1
    
    print(ans)
        
if __name__ == '__main__':
    solve()

Solution (Python):
N, M = map(int, input().split())
Q = [tuple(map(int, input().split())) for _ in range(M)]


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

border = -1
ans = 0

for a, b in Q:
    
    if border <= a:
        ans += 1
        border = b

print(ans)

Solution (Python):
N, M = map(int, input().split())
Q = [tuple(map(int, input().split())) for _ in range(M)]


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

border = []

for a, b in Q:
    flag = True
    for x in border:
        
        if a < x and x <= b:
            flag = False
            break
    if flag:
        border.append(b)

ans = len(border)
print(ans)

Solution (Python):
N,M = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(M)]
l.sort(key=lambda x: x[1])
broken_bridge = 0
position = 0
for i in range(M):
    if position<l[i][0]:
        broken_bridge+=1
        position = l[i][1]-1
print(broken_bridge)

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

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

ans = 0
t = 0
for a, b in ST:
    if a >= t:
        t = b
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
a = []
for i in range(M):
    x, y = map(int, input().split())
    a.append([x, y])
a.sort(key=lambda x: x[1])
ans = 0
for i in range(M-1):
    if a[i+1][0] < a[i][1]:
        a[i+1][1] = a[i][1]
    else:
        ans += 1
ans += 1
print(ans)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)



class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]




n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
c = [[] for i in range(m)]
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c[i] = [a[i], b[i]]
c.sort(key=lambda x:(x[1], x[0]))


right = None
ans = 0
for i in range(m):
    left_now = c[i][0]
    right_now = c[i][1]
    if i == 0:
        right = right_now
        ans += 1
        continue
    if left_now < right:
        continue
    right = right_now
    ans += 1
    
print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

q = []
for ab in AB:
    heapq.heappush(q, ab)

ans = 0
cnt = M
visited = -1
while cnt > 0:
    ab = heapq.heappop(q)
    cnt -= 1

    

    if ab[1] > ab[0]:
        heapq.heappush(q, [ab[1], ab[0]])
        cnt += 1
    else:
        if visited <= ab[1]:
            visited = ab[0]
            ans += 1
        else:
            pass

print(ans)

Solution (Python):

(n,m,),*b=[[*map(int,i.split())]for i in open(0)]
b=sorted(b,key=lambda x:x[1])
p=0
c=0
for i in b:
    if i[0]>=p:
        c+=1
        p=i[1]
    if p == n:
        break
print(c)

Solution (Python):

(n,m,),*b=[[*map(int,i.split())]for i in open(0)]
b=sorted(b,key=lambda x:x[1])
p=0
c=0
for i in b:
    if i[0]>=p:
        c+=1
        p=i[1]
print(c)

Solution (Python):
import sys
input = sys.stdin.buffer.readline





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return 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()))




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

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

	now=0
	ans=0

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

























if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return 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()))




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

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

	now=0
	ans=0

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

























if __name__ == "__main__":
	main()

Solution (Python):
def resolve():
    import sys
    from operator import itemgetter
    
    readline = sys.stdin.readline    

    N, M = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in [0] * M]
    AB.sort(key=itemgetter(1))
    islands = -float('inf')
    ans = 0
    for left, right in AB:
        if islands <= left:
            ans += 1
            islands = right
    print(ans)
    

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from collections import defaultdict, deque, Counter
import math


from bisect import bisect_left, bisect_right





input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def era(n):
    ret = [1 for i in range(n + 2)]
    for i in range(2, int(math.sqrt(n) +3)):
        if ret[i] != 0:
            for j in range(2, n//i + 1):
                ret[i * j] = 0
    rret = []
    for i, r in enumerate(ret):
        if r == 1 and i != 0:
            rret.append(i)

    return rret


def houjyo(n, m, k, kaijyo):
    
    
    if k == n:
        return 1
    else:
        
        ret = nck(n,k,kaijyo) * npk(m-k, n-k, kaijyo) 
        
        return ret % MOD


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def solve():
    n, m = getList()
    kukan = []
    for i in range(m):
        a, b = getList()
        kukan.append((a, b))

    kukan.sort(key=lambda x: x[1])
    
    
    kiru = 0
    ans = 0
    for ku in kukan:
        a, b = ku
        if a >= kiru:
            ans += 1
            kiru = b

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):
import sys

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


def resolve():
    n, m = 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()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N, M = in_nn()
    d = dict()

    for i in range(M):
        a, b = in_nn()
        if a in d:
            d[a] = min(d[a], b)
        else:
            d[a] = b

    edge = list(sorted(d.items(), key=lambda x: x[0], reverse=True))

    remove = deque()
    for a, b in edge:
        if remove:
            if b <= remove[0]:
                remove.appendleft(a)
        else:
            remove.appendleft(a)

    print(len(remove))


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *



N, M = MAP()

ab = [LIST() for _ in range(M)]
ab.sort(key = lambda x: x[1])

ans = 0
tmp = -INF
for l, r in ab:
    if tmp <= l:
        ans += 1
        tmp = r

print(ans)