Charmander has a magical string s whose length is n. At each second, every character in string s expands simultaneously, where character i will become the string Si. That means if the string contains 3 characters c1, c2 and c3, in next second the string will become . But at any moment, each character that appears in string s can only be one of the m characters numbered from 1 to m. Given a target string t, Charmander wants to know in which second it first appears as a substring of string s, or if it never appears?
输入描述:
The input starts with one line containing exactly one integer T, which is the number of test cases.For each test case, the first line contains three integers n, m and k, indicating the length of string s in second 0, the size of character set and the length of string t.Then followed by one line, consisting of n integers, indicating the string s in second 0.Then followed by m lines, each consists of ki, Si[1], , Si[ki], representing the string Si.Then followed by one line, consisting of k integers, indicating the string t.- 1 ≤ T ≤ 10.- 1 ≤ n,m,k ≤ 1000.- .- 1 ≤ s[i], Si[j], t[i] ≤ m.- ki ≥ 2.
输出描述:
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and string t first appears in second y.If string t never appears, y is supposed to be -1.
示例1
输入
2
3 2 4
2 2 2
4 1 2 2 1
5 1 1 2 1 2
1 1 2 1
3 5 1
4 4 3
3 5 4 2
2 1 1
3 4 5 3
2 2 3
3 1 5 4
1
加载中...