Кости и лестницы
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
1.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Кости и лестницы
Игровое поле — полоска из N клеток. Фишка стоит в клетке 1 и хочет попасть в клетку N. За ход бросают кубик (число от 1 до 6) и двигают фишку вперёд на это число клеток; если фишка вышла бы за клетку N, такой бросок невозможен. На m клетках находятся лестницы и змеи: попав на клетку aᵢ, фишка сразу переносится в клетку bᵢ (перенос выполняется один раз, после него ничего не происходит). Можно выбирать результат броска. За какое наименьшее число бросков можно дойти до клетки N?
Ввод. В первой строке N и m (2 ≤ N ≤ 10⁵, 0 ≤ m ≤ N/2). Далее m строк с парами aᵢ bᵢ (2 ≤ aᵢ ≤ N-1, 1 ≤ bᵢ ≤ N, aᵢ ≠ bᵢ, все aᵢ различны).
Вывод. Наименьшее число бросков или -1.
Пример 1
Ввод
10 3
3 9
6 2
8 1
Вывод
2
Комментарии