Степан дуже любить серію фантастичних романів "Гаррі Поттер". Він так сильно нею захоплюється, що входить в групу "Великі любителі Гаррі Потера" та навіть склав збірку всіх заклинань, яким вчать в Гогвартс. Також Степан вивчив всі правила та закономірності цих заклинань.
Самі по собі заклинання нічого не варті, їх потрібно вимовляти в певній послідовності, яка називається комбінацією заклинань.
Ця послідовність має починатись з базового заклинання, та закінчуватись на заклинання, яке називається основним.
Поряд в комбінації можуть йти лише, так звані, спарені заклинання, наприклад, після базового можна промовити лише спарені з ним, Степан вивчив які заклинання є спареними. Комбінація записується як конкатенація заклинань (без проміжків між ними). Степан визначив яким має бути основне (останнє) заклинання в комбінації, тепер він хоче представити свою комбінацію публіці. Для того, щоб група любителів Гаррі Поттера прийняла цю комбінацію, необхідно, щоб її довжина була найменшою серед всіх можливих (адже так простіше буде вчити). Також Степан помітив, що лексикографічно малі комбінації краще приймаються публікою, хто знає, можливо це важливо. Тому необхідно серед всіх можливих найкоротших комбінацій вибрати лексикографічно найменшу. Допоможіть Степану знайти таку комбінацію.
В першому рядку знаходиться два цілих числа і (2 \leq N \leq 1000, 1 \leq M \leq 250000) — кількість заклинань та кількість пар спарених заклинань відповідно. Далі в рядках записані самі заклинання, до того ж, перше заклинання — базове, останнє заклинання — заклинання на яке комбінація має закінуватись. Всі заклинання складаються лише з маленьких літер латинського алфавіту, їх довжини не перевищують 1000 символів. Далі в рядках записано по два різних числа A_i і B_i — номера заклинань, які є спареними. Пари заклинань не повторюються.
В єдиному рядку виведіть шукану комбінацію.
Example 1
Example 2
N \leq 50, назви заклинань з номерами від 1 до складаються з однієї букви — не менше 30 балів
N \leq 50 — не менше 60 балів
N \leq 250 — не менше 75 балів