410708: GYM104081 I 宠物对战

最近 YahAHa 沉迷于一款宠物对战的游戏，这个游戏有两只宠物对战。YahAHa 经常用电脑模拟对战的过程，但最近程序出了问题，于是他碰到了一个问题，他想来问问聪明的你。

现在有两类字符串，$$$A$$$ 类和 $$$B$$$ 类，$$$A$$$ 类字符串有 $$$n$$$ 个，$$$B$$$ 类字符串有 $$$m$$$ 个，每个字符串仅由小写字母组成。用这两类字符串交替拼接可以形成一个新的字符串，形如 $$$abababab$$$……和 $$$bababababa$$$……，其中 $$$a$$$ 表示 $$$A$$$ 类中的某个字符串，$$$b$$$ 表示 $$$B$$$ 类中的某个字符串。注意，同一个字符串可以被重复利用。

现在他有一个字符串 $$$S$$$ ，他想问问你，$$$S$$$ 是否是由 $$$A、B$$$ 两类字符串交替拼接而成（即是否是上述的两种形式之一）。如果是，请输出 $$$S$$$ 最少由多少个字符串拼接而成；如果不是，请输出 -1 。

第一行一个整数 $$$n(1\leq n\leq 10^5)$$$ 表示 $$$A$$$ 类字符串的个数。

接下来 $$$n$$$ 行，每行一个字符串 $$$a_i$$$ 表示 $$$A$$$ 类里的字符串。$$$∑ |a_i|\leq 5\times 10^5$$$

接下来一行一个整数 $$$m(1\leq m\leq 10^5)$$$ 表示 $$$B$$$ 类字符串的个数。

接下来 $$$m$$$ 行，每行一个字符串 $$$b_i$$$ 表示 $$$B$$$ 类里的字符串。$$$∑ |b_i|\leq 5\times 10^5$$$

接下来一行一个字符串 $$$S$$$ 表示 Stump 问你的字符串$$$(1\leq |s|\leq 5000)$$$ 。

一行一个整数表示答案。

1
ccpc
1
female
ccpcfemale

2

2
cc
pc
1
female
ccpcfemale

-1

2
cc
pc
1
female
ccfemalepc

3

2
cc
pc
1
female
femalecc

2