Народ в Пиволенде любит пить пиво. Знаете ли вы, что пиво здесь такое хорошее и сильное, что каждый раз, когда вы пьете его, ваша скорость снижается в десять раз по сравнению с вашей скоростью до его употребления?
Бирко живет в городе Пивграде, но хочет отправиться в город Пивбург. Вам дана дорожная карта Пиволенда и Вам надо найти для него самую быструю дорогу. Когда он начнет свое путешествие в Пивграде, его скорость будет равна 1. Придя в новый город, он всегда пробует стакан местного пива, что делит его скорость на 10.
Вопрос таков: за какое минимальное время он доберется до Пивбурга? Если есть несколько маршрутов с минимальным временем, выберите тот, что содержит наименьшее количество дорог. Если всё равно остается более одного маршрута, выберите любой из них.
Гарантируется, что из Пивграда в Пивбург будет вести не менее одного маршрута.
Выходные данные
В первой строке должно быть записано наименьшее время, необходимое на то, чтобы перейти из Пивграда в Пивбург.
Во второй строке дожны быть записаны номера городов по дороге из Пивграда в Пивбург, занимающей наименьшее время.
В третьей строке выхода должны быть записаны номера городов на этом маршруте в порядке посещения, разделенные пробелами.