VinniS4

Нещодавно Вінні придбав комп’ютер і тепер грає у комп’ютерну гру. Середовищем гри являється пряма лінія. Мета гри: дістатися від старту в точці з координатою 0 до фінішу в точку з координатою n за мінімальну кількість ходів. Ходом вважається перехід на сусідню точку з цілою координатою. У деяких точках прямої знаходяться телепорти, які можуть миттєво перенести гравця в іншу точку прямої. Користуватися телепортами необов’язково, тобто опинившись біля телепорту, гравець може пройти далі не використовуючи його. Гравець може йти лише в напрямку від старту до фінішу (повертатись назад заборонено).

Вінні-Пух хоче дізнатися, який найкращий результат можна показати для кожного з рівнів гри. Напишіть програму, яка дасть відповідь на це запитання.

Технічні умови. Програма VinniS4 читає зі стандартного пристрою введення цілі числа          n (n<=20000) та k – координата фінішу та кількість телепортів відповідно. У k наступних рядках знаходяться описи телепортів: два числа через пробіл a та b, де a –  ціла координата входу, b – ціла координата виходу. Гарантується, що жодна з координат входу/виходу не повторюється та жодна з координат входу/виходу не потрапляє на старт чи фініш рівня. Вхід та вихід телепорту знаходиться обов’язково між стартом та фінішом.

Вихідні дані

Програма виводить на пристрій стандартного виведення мінімальну кількість кроків, яку потрібно зробити для того, щоб пройти даний рівень.

Приклад

Введення 5 0

Виведення 5