Кости и лестницы


Отправить решение Решать в редакторе

Сложность: 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

Комментарии

Еще нет ни одного комментария.