Задача DYVAKNET
Є N комп’ютерів, занумерованих натуральними числами від 1 до N. Розміщені ці комп’ютери в офісі пана Дивака, де не місце стандартним топологіям комп’ютерних мереж. Тому кабелі не ведуть від комп’ютерів до концентраторів (свічів), а з’єднують пари комп’ютерів. Для цього у комп’ютери вставлено по кілька мережевих карт (від 1 до 8). Кожен кабель симетричний, тобто, зв’язуючи k-ий комп’ютер з j-им, зв’язує також і j-ий з k-им. Відомо, що від кожного комп’ютера до кожного існує хоча б один маршрут (який може проходити через проміжні комп’ютери). Природно виникає бажання взнати для кожної пари комп’ютерів маршрут, що проходить через мінімальну кількість проміжних комп’ютерів. Але пану Диваку мало знати один з мінімальних маршрутів – він бажає знати всі.
Напишіть програму, яка знайде всі маршрути між заданими комп’ютерами, які містять однакову мінімальну кількість проміжних комп’ютерів. Маршрути вважаються різними, якщо відрізняються (не дорівнюють одна одній) послідовності проміжних комп’ютерів. Згідно стандартного означення, що послідовності (a1, a2, …, am) та (b1, b2, …, bm) дорівнюють одна одній лише тоді, коли мають однакову довжину та (a1=b1) and (a2=b2) and … and (am=bm).
Технічні умови.
Програма DYVAKNET читає зі стандартного входу (клавіатури) спочатку кількість комп’ютерів N (3≤N≤128), потім кількість кабелів M (N≤M≤4N), далі M пар чисел від 1 до N кожне — номери комп’ютерів, які з’єднує відповідний кабель. Далі йде остання пара різних чисел від 1 до N кожне – номери комп’ютера-старта та комп’ютера-фініша. Старт і фініш не з’єднані безпосередньо. Всі числа записані в одному рядку й розділені одинарними пробілами.
Програма виводить на стандартний вихід (екран) маршрути — послідовності номерів проміжних комп’ютерів. Кожен маршрут слід виводити в окремому рядку, розділяючи номери комп’ютерів всередині маршруту пропусками. Після останнього маршруту треба вивести порожній рядок. Вказувати кількість маршрутів (рядків) не потрібно. Виводити маршрути можна у довільному порядку, але важливо, щоб усі правильні були вказані рівно по одному разу й не був вказаний жоден неправильний. У рядках дозволяються зайві пропуски, але зайві порожні рядки заборонені. Гарантовано, що розміри правильних відповідей не перевищуватимуть 64 Kb.
Приклад
Введення
5 5 5 4 4 3 3 1 1 2 2 4 1 5
Виведення
2 4
3 4