Задача Hoard. Пираты спрятали клад в подземном лабиринте, который состоит из бесконечного количества комнат с каменными стенами. Комнаты имеют номера и соединены переходами, так что все подземелья, если смотреть сверху, выглядит как спираль. Комнаты пронумерованы, как на рисунке. После большого землетрясения некоторые стены разрушились, а между смежными комнатами образовались новые проходы. Вход в лабиринт находится в комнате 1 Кладоискатель знает, что сокровище находится в комнате N. Напишите программу, которая, учитывая расположение клада N и список новых переходов, определяет наименьшее количество переходов, через которые должен пройти искатель, пока доберется до сокровища.
Технические условия. Программа Hoard читает с устройства стандартного ввода в первой строке целое число N (1 ≤ N ≤ 1015) - номер комнаты, в которой расположен сокровище, во второй строке - целое число K (1 ≤ K ≤ 100 000), количество новых переходов . Каждый из следующих K строк содержит одно целое число B (4 ≤ B ≤ 1015), что означает, что теперь новый переход объединяет смежные помещения A и B, где A<B. Номер А не задано явным образом, но его можно однозначно определить по B (например, если B равно 20, то A должно быть 7). Кроме того, в некоторые комнаты никогда не могут быть номером В (номера 2, 3, 5, 7, 10, 13 и т.д.). Программа выводит на устройство стандартного вывода единственное целое число - наименьшее количество переходов, через которые искатель должен пройти, прежде чем он может добраться до сокровища.
Примеры
|
Ввод 31 9 15 25 30 6 9 19 24 27 4
|
Вывод 6 |
Ввод 10000 5 52 4 9 25 27
|
Вывод 9953 |
Пояснение к первому примеру: 1-4-15-14-13-30-31 К сокровищу можно добраться, пройдя 6 проходов |
