Повернуть и переписать
Даны две последовательности целых чисел: A: A_1, A_2, ..., A_n и B: B_1, B_2, ..., B_m, а также набор правил переписывания вида "x_1 x_2 ... x_k → y". Разрешено выполнять следующие преобразования каждой из последовательностей любое количество раз и в любом порядке независимо друг от друга.
Поворот: Перемещение первого элемента последовательности в конец. То есть, преобразование последовательности c_1, c_2, ..., c_p в c_2, ..., c_p, c_1.
Переписывание: Используя правило переписывания "x_1 x_2 ... x_k → y", преобразовать последовательность c_1, c_2, ..., c_i, x_1, x_2, ..., x_k, d_1, d_2, ..., d_j в c_1, c_2, ..., c_i, y, d_1, d_2, ..., d_j.
Ваша задача — определить, возможно ли преобразовать последовательности A и B так, чтобы они стали одинаковыми. Если это возможно, вычислите длину самой длинной из таких последовательностей после преобразования.
Входные данные
Входные данные состоят из нескольких наборов. Каждый набор данных имеет следующий формат.
n m r
A_1 A_2 ... A_n
B_1 B_2 ... B_m
R_1
...
R_r
Первая строка набора данных содержит три положительных целых числа n, m и r, где n (n ≤ 25) — длина последовательности A, m (m ≤ 25) — длина последовательности B, и r (r ≤ 60) — количество правил переписывания. Вторая строка содержит n целых чисел, представляющих элементы A. Третья строка содержит m целых чисел, представляющих элементы B. Каждая из следующих r строк описывает правило переписывания в формате:
k x_1 x_2 ... x_k y
Первое число k — это целое число (2 ≤ k ≤ 10), обозначающее длину левой части правила. Далее следуют k целых чисел x_1, x_2, ..., x_k, представляющих левую часть правила. В конце идет целое число y, представляющее правую часть.
Все числа A_1, ..., A_n, B_1, ..., B_m, x_1, ..., x_k, и y находятся в диапазоне от 1 до 30 включительно.
Строка "0 0 0" обозначает конец ввода.
Выходные данные
Для каждого набора данных, если возможно преобразовать A и B в одну и ту же последовательность, выведите длину самой длинной из таких последовательностей после преобразования. Если это невозможно, выведите -1.