시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 16 1 1 16.667%

문제

최흉최악의 해커 yum3은 팰린드롬에 집착하는 경향이 있다(정작 자신의 이름은 팰린드롬이 아니다).

어느날 yum3은 도시 s에서 출발하여 도시 t로 여행을 떠나게 되었다. 이 세계의 도시와 도시 사이에 있는 모든 길에는 알파벳 대문자가 하나 적혀 있다. 같은 두 도시 사이에 길이 여러 개 존재할 수는 있지만, 시작점과 도착점이 같은 길은 없다.

yum3은 도시 t에 도착할 때까지는 현재 도시에서 인접한 길 중 하나로 균등한 확률로 이동하며, 같은 도시나 길을 여러 번 지나도 상관없다. 단, 도시 t에 도착하거나 도시 t로 갈 수 없는 어떤 도시에 이르게 되면 여행을 즉시 멈춘다. 그리고 t에 도착했으면서 출발지부터 지나온 길에 적혀있던 글자들을 순서대로 나열하여, 만약 그것이 팰린드롬이면 lucky하다고 느낀다. 만약 t에 도착할 수 없게 되거나 경로가 팰린드롬을 이루지 않으면 lucky하지 못하다.

yum3이 lucky한 여행을 할 수 있을 확률은 얼마일까?

입력

첫째 줄에 테스트 케이스의 개수 T(≤ 100)가 주어진다. 이어서 각 테스트 케이스가 여러 줄에 걸쳐 주어진다.

각 테스트 케이스는 빈 줄로 시작하고, 이어서 한 줄에 도시의 개수 n, 길의 개수 m이 주어진다(2 ≤ n ≤ 12, 0 ≤ m ≤1000). 이어서 m개의 줄에 각 길의 정보 정수 u, v(0 ≤ u, v < n, u ≠ v), 알파벳 대문자 w가 주어지는데 이는 도시 u에서 도시 v로 가는 일방향 길이 존재하며 그 길에 적힌 글자가 w라는 의미이다. 이어서 하나의 줄에 질문의 개수를 의미하는 정수 q(≤ 150)가 주어지고, 이어서 q개의 줄에 질문 s, t(0 ≤ s, t < n, s ≠ t)가 주어지는데 이는 출발지가 도시 s, 도착지가 도시 t라는 의미이다.

출력

각 테스트 케이스마다 첫째 줄에 양식에 맞게 테스트 케이스 번호를 출력하고, 이어서 각 줄마다 질문에 대한 답을 출력한다. 각 값은 정답과 10-4 미만의 오차가 나면 정답으로 인정된다.

예제 입력

2

4 3
0 1 A
1 2 A
2 3 A
2
0 3
2 0


5 4
1 2 B
2 3 D
2 4 A
2 0 B
2
1 3
1 0

예제 출력

Case 1:
1.000000
0.000000
Case 2:
0.000000
0.333333

힌트