Problem1009--安全路径

1009: 安全路径

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1554  Solved: 349
[Submit] [Status] [Web Board] [Creator:]

Description

卫斯理小说经常提及外星人,比如蓝血人。 在土星星球有很多城市,每个城市之间有一条或多条飞行通道, 但是并不是所有的路都是很安全的,每一条路有一个安全系数 s,s 是在 01 间的实数 (包括 0 1) ,一条从 u v 的通道 P 的安全度为 Safe(P) = s(e1)*s(e2)*s(ek) e1,e2,ekP 上的边 ,现在蓝血人想出去旅游,面对这这么多的路,他想找一条最安全的路。但是蓝血人的数学不好,想请你帮忙 ^_^ --

Input

输入包括多个测试实例,每个实例包括:

第一行: 一个整数 nn 表示城市的个数 n<=1000;
接着是一个 n*n 的矩阵表示两个城市之间的安全系数, (0可以理解为那两个城市之间没有直接的通道 )

接着是一个整数m (m<=100)表示若干个蓝血人要旅游的路线 ,下面每行有两个数字,表示蓝血人所在的城市和要去的城市。

Output

如果蓝血人无法达到他的目的地,输出 "What a pity!"
其他的输出这两个城市之间的最安全道路的安全系数,保留三位小数。

Sample Input

3
1 0.5 0.5
0.5 1 0.4
0.5 0.4 1
3		
1 2
2 3
1 3

Sample Output

0.500
0.400
0.500