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.
N M U V
x1 x2 ... xn
y1 y2 ... yn
a1 b1 c1
...
au bu cu
au+1 bu+1 cu+1 du+1
...
av bv cv dv
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
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 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 |