改编

内存限制：128 MiB 时间限制：10 Sec

A:“大图书馆是一张n点m边的无向图，Marisa和Patchouli初始分别位于点X和点Y。每分钟，两人都有一次行动机

会：当某人位于点i时，有pi的概率停留在点i，有1-pi的概率等概率随机选择点i的相邻节点之一并前往。若两人

在某个点相遇，则行动停止。值得注意的是，两人在边上是不会相遇的，所以两人在某条边上迎面经过，只会错过

而不会相遇。两人同时行动，求两人在每个点相遇的概率。”

B：“这不是CodeForces 113 D吗，还原度真高啊喂。”

A：“那改一改……不求在每个点相遇的概率，改成求两人在相遇前走过的路径长度期望和。”

B：“大同小异。”

A：“大图书馆的m条边的长度是可以修改的，两人的初始位置也是。”

B：“你不要让Patchouli太累了……”

第一行三个正整数n、m、t，表示点数、边数和数据组数

以下m行，每行2个整数a,b，表示点a和点b之间有一条无向边

接下来一行n个实数表示pi，保证0.01<=pi<=0.99

以下t行，每行前m个整数表示每条边的长度，最后2个整数表示初始位置点X和点Y

1<=n<=22,t<=500，1<=边权<=1000000
保证图是无重边和自环的连通图

共t行，每行一个实数表示两人在相遇前走过的路径长度期望和（保留2位小数）


			4 4 2

1 2

2 3

3 4

1 4

0.5 0.5 0.5 0.5

1 1 1 1 1 2

2 2 2 2 1 3


			4.67

10.67

#3253. 改编