Королівство магів
У королівстві магів з давніх часів є мережа двосторонніх магічних порталів між містами. Кожен портал з'єднує пару міст і дає можливість швидко переміщуватись з одного міста в інше. Міста, які з'єднано магічним порталом, називаються сусідніми.
Принц Альберт та принцеса Бетті живуть у сусідніх містах. З раннього детинства Альберт та Бетті розмовляли один з одним при допомозі магічних куль, які працюють при допомозі магічних порталів між містами.
Альберт та Бетті закохані один в одного. Вони завжди носять з собою кулі, щоб постійно розмовляти один з одним. Проте вони ніколи не бачили один одного і бояться опинитись одночасно у одному і тому ж місті.
Подорож по королівству - це достатньо важка справа для Альберта та Бетті. Їм потрібно подорожувати при допомозі магічних порталів, що достатоньо дорого навіть для королівських сімей. Вони можуть одночасно використовувати пару порталів, щоб переміститись у іншу пару міст, або хтось один з них може використовувати один портал, а інший залишитись у тому ж самому місті. У довільний момент їхньої подорожі вони повинні знаходитись у сусідніх містах. Також вони не можуть одночасно використовувати один і той же портал.
Напишіть програму, яка допоможе Альберту та Бетті переміститись з однієї пари міст в іншу. Потрібно знайти найбільш дешевий план подорожі, тобто мінімізувати кількість переходів через портали. Коли вони переміщуються через два портала одночасно, кількість переходів через портал вважається рівною двом.
Вхідні дані
У першому рядку записані цілі числа n, m, a_1, b_1, a_2, b_2. Туть n (3 ≤ n ≤ 100) - кількість міст у королівстві (міста пронумеровано числами від 1 до n); m (2 ≤ m ≤ 1000) - кількість магічних порталів; a_1,b_1 (1 ≤ a_1, b_1 ≤ n, a_1 ≠ b_1) - номери сусідніх міст, у яких Альберт та Бетті відповідно починають подорож; a_2, b_2 (1 ≤ a_2, b_2 ≤ n, a_2 ≠ b_2) - номери сусідніх міст, куди Альберт та Бетті відповідно хочуть потрапити. (a_1 ≠ a_2 або b_1 ≠ b_2). Наступні m рядків описують портали. У кожному рядку записано два числа p_i1 та p_i2 (1 ≤ p_i1, p_i2 ≤ n, p_i1 ≠ p_i2) - номери міст, з'єднаних порталом. Довільні два міста з'єднано не більше ніж одним порталом.
Вихідні дані
У першому рядку виведіть два числа c та k. Туть c позначає мінімальну кількість використань портала; k позначає кількість пар сусідніх міст, які Альберт та Бетті відвідають під час своєї подорожі, включаючи a_1, b_1 спочатку та a_2, b_2 в кінці. Потім виведіть k рядків, по два цілих числа a'_i та b'_i у кожному - послідовні відмінні пари сусідніх міст, які Альберт та Бетті відвідають протягом подорожі. Якщо є декілька самих дешевих планів подорожі, виведіть довільний з них. Гарантується, що розв'язок існує.