该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

有n个房间，由n-1条隧道连通起来

对于在点i下一步有3种情况：

1：被杀死回到点1 --- 概率为ki%

2：找到出口退出---慨率为ei%

3：沿着边进入下一个点---概率为(1-ki%-ei%)

求从点1开始到退出的平均需要走的边数，即期望值

【输入格式】

第一行输入一个整数T表示有T组数据

对于每组数据的第一行输入一个整数n代表有n个点

接下来输入2n-1行

前的n-1行每行输入两个整数u, v代表u到v有一条边

后n行每行输入两个整数，分别为ki，ei

【输出格式】

对于每一组数据先输出一个字符串Case k: k是数据编号，接着输出一个实数表示求从点1开始到退出的平均需要走的边数，即期望值(结果保留6位小数)

【样例输入】

3
3
1 2
1 3
0 0
100 0
0 100
3
1 2
2 3
0 0
100 0
0 100
6
1 2
2 3
1 4
4 5
4 6
0 0
20 30
40 30
50 50
70 10
20 60

【样例输出】

Case 1: 2.000000
Case 2: impossible
Case 3: 2.895522

【数据范围】

• 对于100%的数据：T <= 30,0 <= Ki, Ei <= 100, Ki + Ei <= 100, K1 = E1 = 0
• 对于40%的数据：2 <= N <= 1000
• 对于60%的数据：2 <= N <= 5000
• 对于100%的数据：2 <= N <= 10000