Черв'яки#541

Черв'яки

3 секунди

64 мегабайти

Середня

Біологи досліджують певний цікавий вид черв'яків. Кожен черв'як може бути представлений як послідовність клітин різних типів. Коли черв'як народжується, він складається лише з однієї клітини. Щодня рівно $1$ клітина черв'яка розростається і перетворюється на $2$ клітини. Визначити вік такого черв'яка дуже просто: він на одиницю менший за кількість клітин, які має черв'як.

Під час росту черв'яка клітина не перетворюється на будь-які $2$ довільні клітини; кожен черв'як має набір "правил росту" (закодованих у його ДНК), яких він дотримується. Правило росту може бути виражене як $A \Rightarrow B C$ A \Rightarrow BC, де $A$ , $B$ і $C$ — великі літери ( $A$ – $T$ ), що представляють різні типи клітин черв'яка. Правило $A \Rightarrow B C$ A \Rightarrow BC означає, що за один день будь-яка окрема клітина $A$ може перетворитись на дві сусідні клітини $B C$ у такому порядку. Зверніть увагу, що правило $I \Rightarrow J K$ I \Rightarrow JK відрізняється від $I \Rightarrow K J$ I \Rightarrow KJ. Різні черв'яки можуть мати різний набір правил росту.

Тепер черв'яки здивували вчених. Через якусь невідому причину деякі черв'яки мутували у новий вид. Цей новий вид черв'яка має ті ж самі властивості, за винятком того, що під час його росту кілька частин тіла можуть рости одночасно. Тобто, щодня будь-яка (принаймні одна, максимум всі) з клітин може рости, і кожна клітина, що росте, перетвориться точно на $2$ клітини (відповідно до правил росту).

У результаті вже не так просто визначити вік черв'яка. Насправді, точний вік деяких черв'яків визначити неможливо. Наприклад, якщо у черв'яка є правила росту: $A \Rightarrow B C$ A \Rightarrow BC, $B \Rightarrow A C$ B \Rightarrow AC, $C \Rightarrow A B$ C \Rightarrow AB, і поточна структура клітин $A C A B$ , то черв'як може бути або $2$ , або $3$ дні ( $A \Rightarrow B C \Rightarrow A C A B$ A \Rightarrow BC \Rightarrow ACAB чи $A \Rightarrow B C \Rightarrow A C C \Rightarrow A C A B$ A \Rightarrow BC \Rightarrow ACC \Rightarrow ACAB). Ваше завдання — визначити найменш можливий вік даного мутованого черв'яка.

Вхідні дані

У вхідних даних буде кілька черв'яків для дослідження. Дані кожного черв'яка починаються з цілого числа $N$ ( $1 \leq N \leq 80$ 1 \le N \le 80), кількості правил росту. Наступні $N$ рядків містять по $3$ великі літери ( $A$ – $T$ ), що представляють правило росту для поточного черв'яка. Перша клітина може вирости в (і бути заміненою) другою і третьою клітинами, у такому порядку, під час росту. Тобто рядок:

$A B C$

означає, що $A \Rightarrow B C$ A \Rightarrow BC є правилом росту для поточного черв'яка.

Наступний (і останній) рядок кожного набору даних містить рядок великих літер ( $A$ – $T$ ). Цей рядок представляє поточну структуру клітин черв'яка. Кожен черв'як у вхідних даних має принаймні $1$ і не більше $50$ клітин.

Останній черв'як буде йти після рядка з одним числом $0$ .

Вихідні дані

Для кожного черв'яка, якщо черв'як може бути вирощений у дану послідовність клітин з даним набором правил росту (починаючи з будь-якої однієї клітини), виведіть мінімальний вік, у днях, черв'яка як ціле число в окремому рядку. Якщо черв'як не може бути вирощений у дану послідовність клітин з даним набором правил (починаючи з будь-якої однієї клітини), то просто виведіть число $- 1$ в окремому рядку. Не друкуйте порожніх рядків між відповідями.

Приклади

Приклад 1