В королевстве магов с древнейших времён есть сеть двусторонних магических порталов между городами. Каждый портал соединяет пару городов и даёт возможность быстро перемещаться из одного города в другой. Города, которые соединены магическим порталом, называются соседними.
Принц Альберт и принцесса Бетти живут в соседних городах. С раннего детства Альберт и Бетти говорили друг с другом с помощью магических шаров, которые работают с помощью магических порталов между городами.
Альберт и Бетти влюблены друг в друга. Они всегда носят с собой шары, чтобы постоянно разговаривать друг с другом. Однако они никогда не видели друг друга и боятся оказаться одновременно в одном и том же городе.
Путешествие по королевству - это достаточно тяжелое дело для Альберта и Бетти. Им нужно путешествовать с помощью магических порталов, что достаточно дорого даже для королевских семей. Они могут одновременно использовать пару порталов, чтобы переместиться в другую пару городов, или кто-то один из них может использовать один портал, а другой остаться в том же самом городе. В любой момент их путешествия они должны находится в соседних городах. Также они не могут одновременно использовать один и тот же портал.
Напишите программу, которая поможет Альберту и Бетти переместиться из одной пары городов в другую. Требуется найти наиболее дешевый план путешествия, то есть минимизировать количество переходов через порталы. Когда они перемещаются через два портала одновременно, количество переходов через портал считается равным двум.
В первой строке записаны целые числа 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 в каждой - последовательные различные пары соседних городов, которые Альберт и Бетти посетят в течение путешествия. Если есть несколько самых дешевых планов путешествия, выведите любой из них. Гарантируется, что решение существует.