0176 - 回転と書換

整数の列 A: A₁ A₂ ... A_n と B: B₁ B₂ ... B_m および "x₁ x₂ ... x_k → y" という形式の書き換えルールがいくつか与えられる． 二つの列に対して独立に以下の変換を，任意の順序で任意回繰り返すことができる．

• 回転: 先頭要素を末尾に動かす．つまり，列 c₁ c₂ ... c_p を c₂ ... c_p c₁ にする．
• 書換: 与えられた書き換えルールに "x₁ x₂ ... x_k → y" があるときに， 列 c₁ c₂ ... c_i x₁ x₂ ... x_k d₁ d₂ ... d_j を c₁ c₂ ... c_i y d₁ d₂ ... d_j にする．

これらの操作を繰り返すことで，A と B を全く同じ列に変形することができるかどうか判定せよ． できる場合は，そのような変形を施した後の列のうちで最長の列の長さを答えよ．

入力は複数のデータセットからなり，各データセットは以下の形をしている．

n m r
A₁ A₂ ... A_n
B₁ B₂ ... B_m
R₁
...
R_r

データセットの最初の行は三つの正整数 n, m, r からなり， n (n ≤ 25) は列 A の長さ， m (m ≤ 25) は列 B の長さ， r (r ≤ 60) は書き換えルールの個数を表す． 次の行には n 個の整数があり，これが列 A の n 個の要素を表す． その次の行には m 個の整数があり，これが列 B の m 個の要素を表す． その次には r 行が以下の形式で続く．各行が一つの書き換えルールに対応する．

k x₁ x₂ ... x_k y

最初の整数 k (2 ≤ k ≤ 10) はルールの左辺の長さである． 次に来る k 個の整数 x₁ x₂ ... x_k はルールの左辺を表す． 最後に来る整数 y はルールの右辺を表す．

A₁, .., A_n, B₁, ..., B_m, x₁, ..., x_k, y はすべて 1 以上 30 以下である．

"0 0 0" と書かれた行が入力の終わりを示す．

各データセットについて， 同じ列に変形できる場合は， そのような変換を施した後の列のうちで最長のものの長さを出力せよ． 同じ列に変形できない場合は，-1 を出力すること．

3 3 3
1 2 3
4 5 6
2 1 2 5
2 6 4 3
2 5 3 1
3 3 2
1 1 1
2 2 1
2 1 1 2
2 2 2 1
7 1 2
1 1 2 1 4 1 2
4
3 1 4 1 4
3 2 4 2 4
16 14 5
2 1 2 2 1 3 2 1 3 2 2 1 1 3 1 2
2 1 3 1 1 2 3 1 2 2 2 2 1 3
2 3 1 3
3 2 2 2 1
3 2 2 1 2
3 1 2 2 2
4 2 1 2 2 2
0 0 0

2
-1
1
9