output_description: Print the minimum number of bridges that must be removed.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      a_1 b_1
      a_2 b_2
      :
      a_M b_M
attempt:     def main():
          # Input
          [N, M] = list(map(int, input().rstrip().split(" ")))
          a, b = [], []
          for i in range(M):
              [_a, _b] = list(map(int, input().rstrip().split(" ")))
              a.append(_a)
              b.append(_b)
          output = solve(N, M, a, b)
          print(output)
       
      def solve(N, M, a, b):
          # 切断したい橋の候補をboolean値で表す
          bool_list = []
          for i in range(M):
              bool_list.append([True if (a[i] <= j+1) and (j+1 < b[i]) else False for j in range(N-1) ])
       
          S = [bool_list]
          counter = 0
          while S:
              C1 = S.pop()
              C2 = []
              l1 = C1.pop(0)
              for l2 in C1:
                  l3 = l1 and l2
                  l3 = [l1[i] and l2[i] for i in range(len(l1))]
                  if sum(l3) == 0:
                      # 積が「すべてFalseになった場合」は別のループを回す
                      C2.append(l2)
                  else:
                      l1 = l3
              if C2:
                  # 別のループを回すためにSにpush
                  S.append(C2)
              counter += 1
          return counter
       
      if __name__ == "__main__":
          main()
problem_description: 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.
samples: [{"input": "5 2\n    1 4\n    2 5", "output": "1\n    \n\nThe requests can be met by removing the bridge connecting the second and third\nislands from the west.\n\n* * *"}, {"input": "9 5\n    1 8\n    2 7\n    3 5\n    4 6\n    7 9", "output": "2\n    \n\n* * *"}, {"input": "5 10\n    1 2\n    1 3\n    1 4\n    1 5\n    2 3\n    2 4\n    2 5\n    3 4\n    3 5\n    4 5", "output": "4"}]