В 2084-м году была построена новая штаб-квартира компании из N этажей, этажи нумеруются от 1 до N. В здании построили K лифтов, каждый из которых ездит по своему отрезку этажей [l_i, r_i], то есть i-й лифт может переместить человека между любыми двумя этажами из отрезка [l_i, r_i]. Перемещаться между этажами здания можно только используя лифты. Гарантируется, что существует способ добраться с любого этажа здания на любой другой.

Из-за этого возникла проблема: главный HR-специалист потребовал установить в некоторых лифтах камеры так, чтобы каждый человек, заходящий в здание на первый этаж и поднимающийся на верхний этаж N, был замечен хотя бы одной камерой. Камера замечает человека, только если он использует лифт, в котором эта камера установлена. Однако покупка каждой камеры требует денег, поэтому нужно разместить как можно меньше камер.

Первая строка содержит два целых числа N и K — количество этажей и лифтов соответственно (1 ≤ N, K ≤ 10⁵).

Следующие K строк содержат по два целых числа l_i и r_i — границы отрезка этажей, по которому ездит i-й лифт (1 ≤ l_i ≤ r_i ≤ N).

Выведите одно число — минимальное количество камер, которое потребуется, чтобы выполнить требование HR-специалиста, или −1, если выполнить требование не возможно.