포레스트 대학교

포레스트 대학교는 학생들에게 학위를 취득하기 위해 모두 수강해야 하는 N개의 과목을 제공한다. 과목은 한 번에 하나씩만 수강할 수 있으며, 다른 과목을 시작하기 전에 한 과목을 이수해야 한다. 각 과목은 사전 지식 없이 수강할 수 있는 기초 과목이거나, 정확히 하나의 다른 과목을 선수 과목으로 요구하는 고급 과목이다.

학생은 어떤 과목을 수강하기 전에 그 과목의 선수 과목을 수강해야 하지만, 두 과목을 반드시 바로 연이어 수강할 필요는 없다. 한 과목이 여러 다른 과목의 선수 과목일 수도 있다. 선수 과목 관계에는 순환이 없다. 선수 과목 규칙을 만족하는 N개 과목의 모든 순서는 학위 취득에 유효하다.

졸업할 때 대학교는 지금까지 수강한 과목의 순서를 축약한 형태로 졸업모에 인쇄하여 기념한다. 더 정확히 말하면, 이 축약된 형태는 수강한 순서대로 각 과목 이름의 첫 글자를 이어 붙인 문자열이다. 예를 들어 Coding 과목을 수강한 뒤 Jamming 과목을 수강했다면 졸업모에는 CJ가 적힌다. 졸업모의 문자열에 특정한 멋진 단어가 부분 문자열로 포함되어 있으면 유행에 맞는 것으로 여겨진다.

과목을 수강할 수 있는 가능한 모든 유효한 순서를 생각하자. 각 멋진 단어에 대해, 해당 졸업모의 문자열에 그 멋진 단어가 적어도 한 번 부분 문자열로 포함되는 순서의 비율을 구해야 한다. 여기서 관심 있는 것은 가능한 서로 다른 졸업모 문자열의 비율이 아니라 가능한 과목 순서의 비율이라는 점에 유의하라. (여러 과목이 같은 글자로 시작할 수 있으므로 가능한 문자열의 수는 과목 순서의 수보다 적을 수 있다.)

Code Jam에서는 다소 이례적으로 이 문제의 근사 답만을 구한다. 출력 형식에 각별히 유의하라.

문제 해결

이 문제에는 작은 입력 1만 있고 큰 입력은 없다. 시간 페널티를 받고 입력을 다시 시도할 수 있다.

제한

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 테스트 세트당 300초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ N ≤ 100. 1 ≤ M ≤ 5. 각 멋진 단어의 길이는 1 이상 20 이하이다. 각 멋진 단어는 영문 대문자로만 이루어진다. 선수 과목 관계로 이루어진 순환은 없다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 다음 내용을 이 순서대로 담은 다섯 줄로 이루어진다.

• 과목의 수 N.

• N개의 정수. 이 정수 중 i번째 정수는 i번째 과목의 선수 과목 번호를 나타내며, i번째 과목이 기초 과목이면 0이다. 과목에는 1부터 N까지 번호가 매겨진다.

• 공백 없이 이어진 N개의 영문 대문자. i번째 문자는 i번째 과목 이름의 첫 글자를 나타낸다.

• 멋진 단어의 수 M.

• 각각 영문 대문자로만 이루어진 M개의 멋진 단어.

각 테스트 케이스마다 Case #x: y_{1} y_{2} ... y_{M}을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y_{i}은 졸업모의 문자열에 i번째 멋진 단어가 부분 문자열로 포함되는 유효한 과목 순서의 비율이다.

y_{i}은 정답과의 절대 오차가 0.03 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고하라.

예제 출력은 예제 케이스에 대해 허용되는 답의 한 세트를 보여 준다. 허용된 정밀도 범위 안에서는 다른 답도 가능하다.

예제 케이스 #1에서 과목 1(C)는 고급 과목 2(J)의 선수 과목인 기초 과목이다. 과목을 모두 이수하는 유일한 방법은 과목 1을 수강한 다음 과목 2을 수강하는 것이다. 그러면 문자열 CJ가 만들어진다. 따라서 멋진 단어 CJ, C, D, JC은 각각 가능한 1가지 경우 중 1, 1, 0, 0가지 경우에서 부분 문자열로 존재한다.

예제 케이스 #2에서 기초 과목 1(B)는 고급 과목 2(A)의 선수 과목이고, 과목 3(A)는 또 다른 기초 과목이다. 과목을 모두 이수하는 방법은 세 가지가 있다.

• 과목 1을 수강하고, 이어서 과목 2을 수강한 다음, 과목 3을 수강한다(문자열: BAA)

• 과목 1을 수강하고, 이어서 과목 3을 수강한 다음, 과목 2을 수강한다(문자열: BAA)

• 과목 3을 수강하고, 이어서 과목 1을 수강한 다음, 과목 2을 수강한다(문자열: ABA)

멋진 단어 AA, AAB, ABA은 각각 가능한 3가지 경우 중 2, 0, 1가지 경우에서 부분 문자열로 존재한다.