Группа студентов задержалась в деканате и очень хочет идти домой. Для этого они хотят составить план, как дойти до аудитории со своими вещами, а затем на улицу. Но так как они слишком сильно устали, они хотят, чтобы этот план был как можно короче.
Представим схему университета множеством мест и списоком пар мест, которые соеденены между собой. Тогда план может быть представлен строкой вида
<место 1> -> <место 2> -> <место 3> -> ... -> <место n>
Среди всех планов найдите такой, что
Первая строка входного файла содержит одну строку — название аудитории с вещами. Оно отличается от названия деканата и улицы.
Далее следуют строки в формате: «<место 1> - <место 2>», означающих, что можно попасть из «места $$$1$$$» в «место $$$2$$$» и наоборот. Количество строк не превосходит $$$101$$$. Названия состоят из строчных латинских букв и знака подчеркивания. Их длина не меньше $$$1$$$ и не больше $$$30$$$.
Гарантируется, что ответ всегда существует.
Выходной файл должен содержать одну строку минимально возможной длины — составленный план.
312_2 deans_office - floor_3 floor_3 - 311 floor_3 - 312 floor_3 - 313 floor_3 - 314 floor_3 - 315 floor_3 - 316 floor_3 - 317 floor_3 - 320 floor_3 - 321 floor_3 - 322 floor_3 - 323 floor_3 - 324 floor_3 - 325 312 - 312_1 312 - 312_2 312 - 312_3 312 - 312_4 floor_3 - floor_2 floor_2 - floor_1 floor_1 - floor_0 floor_0 - street
deans_office -> floor_3 -> 312 -> 312_2 -> 312 -> floor_3 -> floor_2 -> floor_1 -> floor_0 -> street
