팰린드롬 여행

최흉최악의 해커 yum3은 팰린드롬에 집착한다. 정작 자기 이름은 팰린드롬이 아니다.

어느 날 yum3은 도시 s에서 출발해 도시 t까지 여행하기로 했다. 이 세계의 길은 모두 한 방향으로만 통하고, 길마다 알파벳 대문자 하나가 적혀 있다. 같은 두 도시를 잇는 길이 여러 개일 수도 있지만, 출발 도시와 도착 도시가 같은 길은 없다.

yum3은 지금 있는 도시에서 나가는 길 하나를 균등한 확률로 골라 이동한다. 나가는 길이 여러 개면 각 길이 뽑힐 확률은 모두 같고, 같은 도시나 같은 길을 여러 번 지나도 된다. 도시 t에 도착하면 여행이 끝난다. 도착한 도시에서 t까지 가는 경로가 하나도 없으면 그 자리에서 여행을 멈춘다. 출발 도시 s에서 t까지 가는 경로가 없으면 한 걸음도 움직이지 못한다.

t에 도착했다면 지나온 길의 글자를 순서대로 이어 문자열을 만든다. 이 문자열이 팰린드롬이면 yum3은 lucky하다고 느낀다. t에 도착하지 못했거나 문자열이 팰린드롬이 아니면 lucky하지 못하다. 글자가 하나뿐인 문자열도 팰린드롬이다.

yum3이 lucky한 여행을 할 확률을 구하자.

첫째 줄에 테스트 케이스의 개수 T가 주어진다(1 ≤ T ≤ 100).

각 테스트 케이스는 빈 줄로 시작한다. 그 다음 줄에 도시의 개수 n과 길의 개수 m이 주어진다(2 ≤ n ≤ 12, 0 ≤ m ≤ 1000). 도시 번호는 0부터 n-1까지다. 이어지는 m개의 줄에 길의 정보 u, v, w가 주어진다(0 ≤ u, v < n, u ≠ v, w는 알파벳 대문자). 도시 u에서 도시 v로 가는 한 방향 길이 있고 그 길에 글자 w가 적혀 있다는 뜻이다. 같은 (u, v) 쌍이 여러 번 나올 수 있고, 그때는 줄마다 서로 다른 길이다.

그 다음 줄에 질문의 개수 q가 주어지고(1 ≤ q ≤ 150), 이어지는 q개의 줄에 출발 도시 s와 도착 도시 t가 주어진다(0 ≤ s, t < n, s ≠ t).

각 테스트 케이스마다 먼저 Case x:를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 이어서 q개의 줄에 각 질문의 답을 입력 순서대로 출력한다.

답은 yum3이 lucky한 여행을 할 확률이고, 소수점 아래 여섯째 자리까지 반올림해서 출력한다. 확률이 $1/3$이면 0.333333, 1이면 1.000000이다. 테스트 데이터의 모든 답은 반올림 경계에서 $10^{-9}$ 이상 떨어져 있으므로 출력할 문자열은 하나로 정해진다.