유전자형

유전자형(genotype)은 유한한 유전자들의 나열이다. 이는 알파벳 대문자 A–Z로 이루어진 단어로 나타낼 수 있으며, 서로 다른 문자는 서로 다른 종류의 유전자를 뜻한다.

하나의 유전자는 싹을 틔워(budding) 두 개의 새로운 유전자 쌍으로 바뀔 수 있다. 이러한 변환은 유한개의 규칙으로 정해진다. 각 규칙은 세 개의 대문자 $A_1A_2A_3$로 적으며, 이는 유전자 $A_1$이 유전자 쌍 $A_2A_3$으로 바뀔 수 있다는 뜻이다.

문자 S는 초유전자(supergene)라 부르는 특별한 유전자를 나타낸다. 유전자형의 배양은 초유전자들의 나열에서 시작하여, 주어진 규칙에 따라 원하는 유전자를 반복해서 싹틔우는 방식으로 진행된다.

여러 개의 유전자형이 주어질 때, 각 유전자형이 어떤 유한한 초유전자 나열로부터 배양될 수 있는지 판정하고, 가능하다면 그러한 나열에 필요한 초유전자의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 10000$). 다음 $n$개의 줄에는 각각 하나의 싹틔우기 규칙이 대문자 A–Z 세 글자로 된 단어로 주어진다. 규칙의 둘째 또는 셋째 글자는 초유전자일 수도 있다.

그다음 줄에 정수 $k$가 주어진다 ($1 \le k \le 10000$). 다음 $k$개의 줄에는 각각 하나의 유전자형이 주어지며, 이는 최대 $100$글자의 대문자 A–Z로 이루어진 비어 있지 않은 단어이다.

$i$번째 유전자형에 대해 다음 중 하나를 한 줄에 출력한다.

• 그 유전자형을 배양할 수 있는 초유전자 나열의 최소 개수(양의 정수), 또는
• 배양이 불가능하면 NIE(폴란드어로 "아니오").