Задача DYVAKNET

N компьютеров пронумерованы натуральными числами от 1 до N. Они расположены в офисе господина Дывака, где нет места стандартным топологиям компьютерных сетей. Поэтому кабеля не соединяют компьютеры с концентраторами (свичами), а связывают компьютеры попарно. При этом в каждом компьютере установлено несколько сетевых карт (от 1 до 8). Каждый кабель является симметричным, то есть, соединяя k-ый компьютер с j-ым, он соединяет также и j-ый с k-ым.

Известно, что каждая пара компьютеров объединена между собой хотя бы одним маршрутом (который может проходить через промежуточные компьютеры). Естественным является желание узнать для каждой пары компьютеров маршрут, проходящий через минимальное количество промежуточных компьютеров. Но господин Дывак желает узнать не один из минимальных маршрутов, а все.

Напишите программу, которая найдет все маршруты между заданными  компьютерами, содержащие одинаковое минимальное количество промежуточных компьютеров. Маршруты считаются разными, если отличаются (не равны друг другу) последовательности промежуточных компьютеров. Согласно стандартному определению, последовательности (a₁, a₂, …, a_m) и (b₁, b₂, …, b_m) равны друг другу только тогда, когда имеют одинаковую длину и (a₁=b₁) and (a₂=b₂) and … and (a_m=b_m).

Технические условия.

Программа 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