4299 - Randomly-priced Tickets Europe - Southwestern - 2008/2009
	PDF	Submit	Ranking

Al final de la Edad media, se han fundado ya varias universidades a lo largo de Europa. El nuevo término simplemente ha empezado, hay muchos novatos así que alrededor. No todos hemos tenido suerte ser admitido a su universidad deseada. Como resultado, muchas parejas están viviendo ahora en los pueblos separados.  

Claro, ellos intentan vernos tan a menudo como ellos pueden. Facilitar esto, los estudiantes han negociado un trato con los cocheros. En lugar de pagar el precio regular por un paseo de un pueblo a otro, el precio es determinado dibujando un entero aleatorio entre 1 e inclusivamente, todos los números que son igualmente probables.

Desgraciadamente, este proceso se repite unas veces siempre que no hay ninguna conexión directa entre los pueblos en que una pareja vive. Eso hace el costo total de una jornada bastante imprevisible.  

Ayude a las parejas a determinar la probabilidad que uno de ellos puede permitirse el lujo de un viaje sentido único al otro. Dado el número de pueblos y una lista de conexiones directas, se supone que su programa procesa una lista de parejas. Para cada pareja, usted sabe su presupuesto y donde ellos viven. Claro, ellos siempre escogerán una ruta con el precio esperado. Tal ruta existe entre cualquier de los dos pueblo.

Input
La primera línea contiene el número de casos de la prueba que siguen.

Cada caso de la prueba empieza con una línea que sostiene el número  pueblos  ( ) seguido por el precio máximo de un solo boleto ( ). Lo siguiente las líneas contienen  carácteres cada uno. El carácter en él , la línea de éstos es “Y”, si hay una conexión directa entre los pueblos  y , pero “N” por otra parte. El carácter en él ,  la línea siempre es igual que el carácter en . El -th caracter en él , la línea siempre es “N”.

Cada caso de la prueba sigue con el C del número de parejas en una línea solo ( ). Cada caso de la prueba sigue con el C del número de parejas en una línea solo  

Hay una línea que sostiene tres a, b de los enteros entonces para cada pareja, y m. Estos estado de los números que uno de ellos las vidas en el pueblo un, el otro en el pueblo b (, ), y la cantidad de dinero que ellos pueden gastar es m( ).

Output
Entonces, rendimiento una línea para cada pareja en este caso de la prueba que contiene la probabilidad que ellos pueden permitirse el lujo de una jornada sentido único anteriormente según las reglas. Su respuesta se permite diferir a lo sumo del resultado exacto por . Imprima una línea pálida después de cada caso de la prueba.

Sample Input

2
3 4
NYY
YNY
YYN
1
1 3 1
4 7
NYNN
YNYN
NYNY
NNYN
2
1 3 10
1 4 10

Sample Output

Case 1
0.250000

Case 2
0.795918
0.341108

---

Southwestern 2008-2009

Traducido por: Lázaro Roldán, Edgar Alexis