Gluing Pictures
By Nicolás Álvarez 
Argentina
By Nicolás Álvarez Argentina
Enzo recently traveled to the city of Montevideo, where he saw a big sign with the name of the city. He decided to take pictures of the sign to make a collage and send it to his friend Demonio. Enzo wants to form the name of his friend by taking one or several pictures of sections of the sign. For example, with the string “MONTEVIDEO”, he might form the name of his friend by
putting together “DE-MON-I-O”, using four pictures to form the entire name. It is easy to show that the result cannot be achieved with fewer pictures.
You will be given the name of a city and a list of friends’ names. Return the minimum number of pictures needed to form the name of each friend. When forming the names, pictures cannot be rotated, reflected or modified in any way.
The first line contains a string C indicating the name of the city. The second line contains a positive integer N representing the number of friends. Each of the following N lines contains a string indicating the name of a friend. All strings are non-empty and consist only of uppercase letters. The sum of the lengths of all strings is at most 2 × 105.
Output N lines, each line with an integer indicating the minimum number of needed pictures to form the corresponding name in the input, or the value “-1” if it is not possible to generate the name.
| Input Samples | Output Samples |
|
MONTEVIDEO |
4 |
|
SANTIAGO |
3 |