GENOTYPES

Time Limit:1000ms Memory Limit:64000KiB
Accepted:0 Submitted:0
GENOTYPES

POI IV Stage II Problem 2

Genotypes

Genotype is a finite sequence of genes. It can be described by words built of capital letters A-Z of the English alphabet. Different letters denote different kinds of genes. A gene can bud and in effect transform into a pair of new genes. Such transformations are controlled by a finite set of rules. Every rule of budding can be described by three capital letters A1A2A3. Such a description means that gene A1 can transform into the pair of genes A2A3.

We are using S to denote the special kind of genes called supergenes. The breeding of a genotype begins from a sequence of supergenes and it consists in controlled budding of chosen genes according to the given rules.

Task

Write a program that:
  • reads from the text file GEN.IN a finite set of budding rules and a sequence of words describing genotypes which we want to breed,
  • for every given genotype checks if it can be bred from a certain finite sequence of supergenes according to the given budding rules and if so finds the minimal length of such a sequence,
  • writes the result to the text file GEN.OUT.

Input

In the first line of the text file GEN.IN there is one integer n, 1 <= n <= 10000. In each of the following n lines there is one budding rule. Such a rule is described by a word consisting of three capital letters A - Z.

In the next line there is written one integer k, 1 <= k <= 10000. In each of the following k lines there is one genotype. Such a genotype is described by a non-empty word consisting of at most 100 letters A - Z.

Output

In the i-th of k lines of the text file GEN.OUT there should be written:
  • one positive integer - the minimal length of a sequence of supergenes needed to breed the i-th of the given genotypes, or
  • the word NIE (which means NO in Polish), if such a genotype can not be bred.

Example

For the file GEN.IN:
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA
the correct solution is file GEN.OUT:
3
1
NIE

SubmitStatistics

SOJ is designed and developed by Wilbur Ding and Liang Sun. ©All Rights Reserved 2009-2012.