Warp Speed
В недалеком будущем космические инженеры могут изобрести новую технологию для космических путешествий и назвать её "варп-двигатель". Этот варп-двигатель позволяет космическому кораблю двигаться быстрее скорости света, изгибая определённое расстояние в космосе и позволяя кораблю перемещаться через это изогнутое пространство за один "прыжок". Поскольку время, затраченное на каждый прыжок, одинаково, общее время путешествия для любого космического корабля (оснащённого этим варп-двигателем) зависит от количества прыжков, которые он совершает. Более того, инженеры заметили, что расстояние прыжка зависит от некоторых видов силовых полей в пространстве, где этот прыжок осуществляется. Чтобы переместиться от начальной до конечной точки, космический корабль может пройти через множество силовых полей, что может потребовать множества прыжков.
Из своих экспериментов они обнаружили следующие факты:
- Количество типов силовых полей довольно мало. - Поэтому для обозначения каждого из этих типов силовых полей можно использовать одну английскую букву. - Космический корабль может пройти через каждое отдельное силовое поле за один прыжок. - Космический корабль может пройти через определённые последовательности из двух или более силовых полей за один прыжок. Эти определённые последовательности хранятся как правила последовательностей, которые можно пройти за один прыжок. - Пример списка этих правил показан в следующей таблице.
В этом примере есть **4** правила, что означает, что космический корабль может пройти через каждое из них, используя один прыжок. Первое правило — "**ab**", что означает, что космический корабль может пройти через силовые поля '**a**' и '**b**' за один прыжок. Второе правило — "**abcd**", что означает, что он может пройти через '**a**', '**b**', '**c**' и '**d**' за один прыжок.
Обратите внимание, что в этом примере нет последовательности/правила "**abc**", поэтому, хотя корабль может пройти через последовательность "**abcd**", он не может пройти через "**abc**" (за один прыжок). Ему нужно сделать **2** прыжка: первый прыжок — пройти через последовательность "**ab**", а второй — через силовое поле "**c**".
**Цель**
Предположим, что вы инженер на боевом космическом корабле. Ваша задача — провести ваш космический корабль через космос как можно быстрее. Ваш корабль оснащён зондом, который может идентифицировать последовательность силовых полей на пути к вашей цели. Чтобы выполнить свою задачу, вам нужно создать компьютерную программу, которая найдёт минимальное количество прыжков на основе правил и любых заданных последовательностей силовых полей.
Входные данные
Входные данные состоят из стандартного ввода, содержащего **2** части данных, которые разделены пустой строкой.
Первая часть — это набор правил последовательностей, которые можно пройти за один прыжок. Количество правил находится в диапазоне от **1** до **10000**.
- Каждая строка в этой первой части содержит одно правило. - Каждое правило — это (под)последовательность силовых полей, заданная строкой из букв алфавита (**a-z**, **A-Z**). - Порядок в каждой (под)последовательности идёт слева направо. - Размер любой (под)последовательности находится в диапазоне от **2** до **20**.
Вторая часть — это набор силовых полей вдоль пути, который космический корабль должен пройти. Количество последовательностей находится в диапазоне от **1** до **200**.
- Каждая строка во второй части содержит одну последовательность силовых полей на одном пути. - Каждая последовательность задана строкой из букв алфавита (**a-z**, **A-Z**). - Порядок в каждой последовательности идёт слева направо. - Размер любой последовательности находится в диапазоне от **2** до **500**.
Пустая строка после второй части является окончанием ввода.
Выходные данные
Для каждой последовательности во второй части ввода напишите **2** части вывода следующим образом:
- В первой строке напишите общее количество решений, за которым следует пробел и количество минимальных прыжков. - В следующих строках напишите каждое из решений в каждой строке. Каждое решение содержит последовательность силовых полей, как указано во входных данных, где пробел вставляется между каждой подпоследовательностью прыжка. Если есть два или более решений, они должны быть отсортированы в порядке возрастания и лексикографическом (ASCII) порядке.
**Дополнительные объяснения**
В этом примере **5** правил и **5** входных последовательностей.
В первом примере вывода есть 1 решение с **2** прыжками. Первый прыжок — из первого правила.
Во втором выводе есть **1** решение с **1** прыжком, используя второе правило для всей последовательности.
В третьем выводе есть **2** решения с **2** прыжками. Первое решение — из **4**-го правила, а второе решение — из **3**-го правила.
В четвёртом выводе есть **4** решения с **4** прыжками. Первое решение применяется с использованием **4**-го правила дважды. Второе и третье применяются с использованием **3**-го и **4**-го правил в разных позициях.
Последнее решение применяется с использованием **3**-го правила дважды. Последний вывод очень похож на четвёртый, но также применяется с пятым правилом в середине последовательности.