Genome Splicing
本题没有可用的提交语言。
Description
Spunch Bob has big dreams for the jellyfishing competition coming up. In this competition, jellyfishers show off their best catch to be judged by the audience.
Plankton has a sneaky plan to win this competition. Instead of catching a jellyfish, he decides he can just make one. In particular, since he knows what aspects of a jellyfish (transparency, size, number of tentacles) are preferred, he plans to splice together the DNA of existing jellyfish in order to create an award-winning jellyfish.
This process works as follows. Plankton has a string consisting of the uppercase letters "A, T, C, G", representing the desired genome of the award-winning jellyfish.
Plankton also has segments of DNA recovered from other jellyfish, also represented as strings with the letters "A, T, C, G." These segments can be concatenated together to form longer strands of DNA; furthermore, any segment can be used as many times as desired.
Plankton wants to know: what is the minimum number of segments required to build the desired genome (the concatenated segments must match the genome exactly)?
Furthermore, Plankton has an additional restriction: he knows it will look suspicious if the same segment of DNA is used twice in a row, i.e., the same segment is concatenated to itself with nothing in between. What is the minimum number of segments required to build the desired genome subject to this restriction?
The first line contains a single integer $N$, denoting the number of segments. ($1 \le N \le 10^3$)
The second line contains a single string $G$ ($1 \le |G| \le 10^3$), representing the desired genome.
The next $N$ lines each contain a single string $s_i$ ($1 \le |s_i| \le 10^3$), representing the component segments. It is guaranteed that all segments will be distinct.
All segments and the genome will consist of only the uppercase letters "A, T, C, G".
Output a single integer: the minimum number of segments required to match the desired genome exactly, or -1 if it is not possible.
Input
The first line contains a single integer $N$, denoting the number of segments. ($1 \le N \le 10^3$)
The second line contains a single string $G$ ($1 \le |G| \le 10^3$), representing the desired genome.
The next $N$ lines each contain a single string $s_i$ ($1 \le |s_i| \le 10^3$), representing the component segments. It is guaranteed that all segments will be distinct.
All segments and the genome will consist of only the uppercase letters "A, T, C, G".
Output
Output a single integer: the minimum number of segments required to match the desired genome exactly, or -1 if it is not possible.
6
ATTACAGA
AT
TA
T
ACAGA
C
AGA
6
ATTTACAGACA
AT
TTA
T
ACAGACA
CA
GA
1
ACTG
A
3
5
-1