Группа студентов задержалась в деканате и очень хочет идти домой. Для этого они хотят составить план, как дойти до аудитории со своими вещами, а затем на улицу. Но так как они слишком сильно устали, они хотят, чтобы этот план был как можно короче.

Представим схему университета множеством мест и списоком пар мест, которые соеденены между собой. Тогда план может быть представлен строкой вида

<место 1> -> <место 2> -> <место 3> -> ... -> <место n>

Среди всех планов найдите такой, что

1. для каждого i от $$$1$$$ до $$$n-1$$$ возможно непостредствено перейти из <место i> в <место i + 1>;
2. строка не содержит ведущих и концевых пробелов;
3. каждая стрелка окружена ровно одним пробелом;
4. название деканата — «deans_office»;
5. название улицы — «street»;
6. план содержит строки «deans_office», «street» и название аудитории с вещами ровно один раз;
7. план начинается со строки «deans_office» и заканчивается строкой «street»;
8. количество символов в строке минимально возможно.