회전과 재작성

정수 수열 두 개와 재작성 규칙 여러 개가 주어진다. 수열 A는 $A_1, A_2, \ldots, A_n$이고 수열 B는 $B_1, B_2, \ldots, B_m$이며, 각 규칙은 $x_1, x_2, \ldots, x_k \to y$ 꼴이다. 두 수열에는 아래 두 변환을 원하는 순서로 원하는 횟수만큼 적용할 수 있고, 두 수열은 서로 독립적으로 변환한다.

• 회전: 수열의 첫 원소를 맨 뒤로 옮긴다. 즉 $c_1, c_2, \ldots, c_p$를 $c_2, \ldots, c_p, c_1$로 바꾼다.
• 재작성: 규칙 $x_1, x_2, \ldots, x_k \to y$를 써서 $c_1, c_2, \ldots, c_i, x_1, x_2, \ldots, x_k, d_1, d_2, \ldots, d_j$를 $c_1, c_2, \ldots, c_i, y, d_1, d_2, \ldots, d_j$로 바꾼다.

A와 B를 같은 수열로 만들 수 있는지 판정하고, 만들 수 있다면 그렇게 만든 수열의 길이 중 가장 큰 값을 구하라.

입력은 여러 데이터 집합으로 이루어진다. 각 데이터 집합의 형식은 다음과 같다.

n m r
A1 A2 ... An
B1 B2 ... Bm
R1
...
Rr

첫 줄에는 양의 정수 $n$, $m$, $r$가 주어진다. $n$은 수열 A의 길이($n \le 25$), $m$은 수열 B의 길이($m \le 25$), $r$는 재작성 규칙의 개수($r \le 60$)다. 둘째 줄에는 A의 원소 $n$개가, 셋째 줄에는 B의 원소 $m$개가 주어진다. 이어지는 $r$개 줄은 각각 규칙 하나를 다음 형식으로 나타낸다.

k x1 x2 ... xk y

맨 앞의 $k$는 규칙 좌변의 길이이고 $2 \le k \le 10$이다. 그 뒤에 좌변을 이루는 정수 $k$개 $x_1, x_2, \ldots, x_k$가 오고, 마지막에 우변을 나타내는 정수 $y$가 온다.

$A_1, \ldots, A_n$, $B_1, \ldots, B_m$, $x_1, \ldots, x_k$, $y$는 모두 1 이상 30 이하다.

0 0 0인 줄이 입력의 끝을 나타낸다.

각 데이터 집합마다 한 줄씩 출력한다. A와 B를 같은 수열로 만들 수 있으면 그렇게 만들 수 있는 수열의 최대 길이를 출력하고, 만들 수 없으면 -1을 출력한다.