Швидкість Ворп
У недалекому майбутньому космічні інженери можуть винайти нову технологію для подорожей у космосі, яку назвуть "варп-двигун". Цей варп-двигун дозволяє космічному кораблю подорожувати швидше за швидкість світла, згинаючи певну відстань у космосі, що дозволяє кораблю подолати цей зігнутий простір за один "стрибок". Оскільки час, витрачений на кожен стрибок, однаковий, загальний час подорожі для будь-якого космічного корабля (оснащеного цим варп-двигуном) залежить від кількості стрибків, які він здійснює. Крім того, інженери виявили, що відстань стрибка залежить від певних силових полів у космосі, через які здійснюється стрибок. Щоб подорожувати від початкової до кінцевої точки, космічний корабель може пройти через багато силових полів, що може вимагати здійснення багатьох стрибків.
З їхніх експериментів вони виявили такі факти:
Кількість типів силових полів є досить малою.
Тому для позначення кожного з цих типів силових полів можна використовувати одну англійську літеру.
Космічний корабель може пройти через кожне окреме силове поле за один стрибок.
Космічний корабель може пройти через певні послідовності двох або більше силових полів за один стрибок. Ці певні послідовності зберігаються як правила послідовностей, які можна пройти за один стрибок.
Приклад списку цих правил наведено в наступній таблиці.
У цьому прикладі є 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-є правило двічі. Останній вихід дуже схожий на четвертий, але також застосовується з п'ятим правилом посередині послідовності.