513010 - 迷宫

【题目描述】迷宫（maze）

小光发现自己陷入了一个巨大的迷宫，初始时小光在1号房间。 迷宫由N个房间和连接这些房间的通道组成，每对房间都通过一条且只有一条通道连接。当小光踏入一个房间时，他有可能掉入该房间的陷阱并送回1号房间。也有可能找到该房间的隐藏出口逃离这个迷宫。 小光对整个迷宫的结构一无所知，因此，他每次只是随机选择一条通道。当他在一个房间里时，他有同样的可能性选择连接该房间的任何通道（包括他过去来该房间的通道）。 试计算在他找到出口之前，预计要经过多少通道。

第一行是一个整数T（T≤30），表示测试用例的数量。 每种测试用例第一行都是一个整数N（2≤N≤10000），表示房间数量。 然后给出N-1对整数X，Y（1≤X，Y≤N，X≠Y），表明X和Y之间存在一条通道。 最后，给出了N对整数Ki和Ei（0≤Ki，Ei≤100，Ki+Ei≤100%，K1=E1=0），表示第i个房间掉入陷阱的概率和找到隐藏出口逃离迷宫的概率。

对于每个测试用例，输出一行“case k:”。k是case id，然后是退出之前经过的预期通道数（保留小数点后5位）。如果无法逃离迷宫，则输出“不可能”。