Rats

You are given an infinite line covered with a periodically repeating string $A$. There are infinitely many concatenated copies of the string $A$ on the line. The line has no beginning and no end. You are also given a set $S$ of $M$ strings. You must build a new string $B$ by concatenating strings from $S$. The string $B$ must satisfy the following conditions:

• After covering a new empty infinite line with infinitely many concatenations of the string $B$, the line must be identical to the line covered with $A$.
• If there are several valid strings $B$ or several valid ways to build $B$, choose $B$ and its construction that use the fewest strings from $S$.

You may use the same string from $S$ several times, but each use counts as a new string. You may concatenate the strings in any order, but you may not change the order of letters inside a string. If no string $B$ can be built, print $-1$.

• The first line contains the string $A$ $(1\leq |A| \leq 500)$.
• The second line contains the integer $M$ $(1 \leq M \leq 10^5)$, the number of strings in the set $S$.
• Each of the next $M$ lines contains one string from $S$. The $i$-th line contains the string $L_i$ $(1 \leq |L_i| \leq |A|)$.
• The sum of the lengths of the strings in $S$ is at most $10^6$ $(\sum_{i=1}^{M} |L_i| \leq 10^6)$.

Print one integer: the minimum number of strings from $S$ needed to build the string $B$.

You can use one string "b" and two strings "a" to build $B$ = "aba":

• ...baabaabaabaa...
• .....abaabaabaaba...