TRANS - Transformation

You are given two short sequences of numbers, X and Y. Try to determine the minimum number of steps of transformation required to convert sequence X into sequence Y, or determine that such a conversion is impossible.

In every step of transformation of a sequence, you are allowed to replace exactly one occurrence of one of its elements by a sequence of 2 or 3 numbers inserted in its place, according to a rule specified in the input file.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case, the first line of input contains four integers - N, M, U, V (1<=N,M<=50). The next two lines of input contain sequences X and Y, consisting of N and M integers respectively. The next U lines contain three integers: a b c each, signifying that integer a can be converted to the sequence b c in one step of transformation. The next V-U lines contain four integers: a b c d each, signifying that integer a can be converted to the sequence b c d in one step of transformation. With the exception of N and M, all integers provided at input are positive and do not exceed 30.

The format of one set of input data is illustrated below.

Output

For each test case output -1 if it is impossible to convert sequence X into sequence Y, or the minimum number of steps required to achieve this conversion otherwise.

Example

Sample input:
1
3 10 2 3
2 3 1
2 1 1 2 2 1 2 1 2 1
3 1 2
3 3 3
3 1 3 2

Sample output:
6

Added by:adrian
Date:2004-07-18
Time limit:1.076s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:based on a problem from the VI Polish Collegiate Team Programming Contest (AMPPZ), 2001

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.