In the year 2084, a new headquarters of a company was built with N floors, numbered from 1 to N. In the building, K elevators were installed, each of which serves its segment of floors [l_i, r_i], meaning that the i-th elevator can transport a person between any two floors within the segment [l_i, r_i]. Movement between the floors of the building can only be done using the elevators. It is guaranteed that there is a way to get from any floor in the building to any other floor.

Due to this, a problem arose: the chief HR specialist demanded that cameras be installed in some elevators so that every person entering the building on the first floor and ascending to the top floor N is detected by at least one camera. A camera detects a person only if they are using the elevator in which the camera is installed. However, purchasing each camera requires money, so the goal is to place as few cameras as possible.

The first line contains two integers N and K — the number of floors and elevators, respectively (1 ≤ N, K ≤ 10⁵).

The next K lines contain two integers l_i and r_i — the boundaries of the segment of floors that the i-th elevator serves (1 ≤ l_i ≤ r_i ≤ N).

Output a single number — the minimum number of cameras required to meet the HR specialist’s requirement, or −1 if it is not possible to meet the requirement.