Поверніть і Перепишіть#6107

Поверніть і Перепишіть

8 секунд

64 мегабайти

Дуже складна

Дано дві послідовності цілих чисел $A$ : $A_{1}$ A_1 $A_{2}$ A_2 ... $A_{n}$ A_n та $B$ : $B_{1}$ B_1 $B_{2}$ B_2 ... $B_{m}$ B_m, а також набір правил переписування у вигляді " $x_{1}$ x_1 $x_{2}$ x_2 ... $x_{k}$ x_k → $y$ ". Ви можете виконувати наступні перетворення над кожною з послідовностей необмежену кількість разів у будь-якому порядку незалежно.

Обертання: Переміщення першого елемента послідовності в кінець. Тобто, перетворення послідовності $c_{1}$ c_1 $c_{2}$ c_2 ... $c_{p}$ c_p на $c_{2}$ c_2 ... $c_{p}$ c_p $c_{1}$ c_1.
Переписування: За правилом переписування " $x_{1}$ x_1 $x_{2}$ x_2 ... $x_{k}$ x_k → $y$ ", перетворення послідовності $c_{1}$ c_1 $c_{2}$ c_2 ... $c_{i}$ c_i $x_{1}$ x_1 $x_{2}$ x_2 ... $x_{k}$ x_k $d_{1}$ d_1 $d_{2}$ d_2 ... $d_{j}$ d_j на $c_{1}$ c_1 $c_{2}$ c_2 ... $c_{i}$ c_i $y$ $d_{1}$ d_1 $d_{2}$ d_2 ... $d_{j}$ d_j.

Ваше завдання - визначити, чи можливо перетворити дві послідовності $A$ та $B$ в одну й ту ж послідовність. Якщо це можливо, обчисліть довжину найдовшої з послідовностей після такого перетворення.

Вхідні дані

Вхід складається з кількох наборів даних. Кожен набір даних має наступну структуру.

$n$ $m$ $r$

$A_{1}$ A_1 $A_{2}$ A_2 ... $A_{n}$ A_n

$B_{1}$ B_1 $B_{2}$ B_2 ... $B_{m}$ B_m

$R_{1}$ R_1

...

$R_{r}$ R_r

Перший рядок набору даних складається з трьох додатних цілих чисел $n$ , $m$ та $r$ , де $n$ ( $n \leq 25$ n \le 25) - це довжина послідовності $A$ , $m$ ( $m \leq 25$ m \le 25) - це довжина послідовності $B$ , і $r$ ( $r \leq 60$ r \le 60) - це кількість правил переписування. Другий рядок містить $n$ цілих чисел, що представляють $n$ елементів $A$ . Третій рядок містить $m$ цілих чисел, що представляють $m$ елементів $B$ . Кожен з останніх $r$ рядків описує правило переписування у наступній формі.

$k$ $x_{1}$ x_1 $x_{2}$ x_2 ... $x_{k}$ x_k $y$

Перше $k$ - це ціле число ( $2 \leq k \leq 10$ 2 \le k \le 10), яке є довжиною лівої частини правила. За ним слідують $k$ цілих чисел $x_{1}$ x_1 $x_{2}$ x_2 ... $x_{k}$ x_k, що представляють ліву частину правила. Нарешті йде ціле число $y$ , що представляє праву частину.

Всі з $A_{1}$ A_1, .., $A_{n}$ A_n, $B_{1}$ B_1, ..., $B_{m}$ B_m, $x_{1}$ x_1, ..., $x_{k}$ x_k, та $y$ знаходяться в діапазоні від $1$ до $30$ включно.

Рядок " $0$ $0$ $0$ " позначає кінець вводу.

Вихідні дані

Для кожного набору даних, якщо можливо перетворити $A$ та $B$ в одну й ту ж послідовність, виведіть довжину найдовшої з послідовностей після такого перетворення. Виведіть $- 1$ , якщо це неможливо.

Приклади

Приклад 1