{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e当lxhgww醒来时,发现自己身处一个巨大的迷宫。\u003cbr\u003e\u003cbr\u003e这个迷宫由N个房间和连接这些房间的隧道组成。每一对房间之间只有一条路径相连。最初,lxhgww位于1号房间。每个房间都设有危险陷阱。当lxhgww踏入一个房间时,有可能被杀死并重新从1号房间开始。每个房间也都设有一个隐藏的出口。每次lxhgww来到一个房间时,都有机会找到出口并逃离这个迷宫。\u003cbr\u003e\u003cbr\u003e不幸的是,lxhgww对整个迷宫的结构一无所知。因此,他每次只是随机选择一个隧道。当他在一个房间时,他有同样的可能性选择连接该房间的任何隧道(包括他用来来到该房间的隧道)。\u003cbr\u003e在找到出口之前,他要经过多少条隧道?\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行是一个整数T(T ≤ 30),表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e每个测试用例的开头是一个整数N(2 ≤ N ≤ 10000),表示该测试用例中房间的数量。\u003cbr\u003e\u003cbr\u003e然后给出N-1对整数X,Y(1 ≤ X,Y ≤ N,X ≠ Y),表示房间X和房间Y之间有一条隧道相连。\u003cbr\u003e\u003cbr\u003e最后,给出N对整数Ki和Ei(0 ≤ Ki,Ei ≤ 100,Ki + Ei ≤ 100,K1 \u003d E1 \u003d 0),表示第i个房间中被杀死和找到出口的可能性百分比。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行“Case k: ”。k是测试用例编号,然后是lxhgww在找到出口之前经过的隧道数的期望值。答案的相对误差小于0.0001将被接受。如果无法从迷宫中逃脱,则输出“impossible”。\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3\r\n1 2\r\n1 3\r\n0 0\r\n100 0\r\n0 100\r\n3\r\n1 2\r\n2 3\r\n0 0\r\n100 0\r\n0 100\r\n6\r\n1 2\r\n2 3\r\n1 4\r\n4 5\r\n4 6\r\n0 0\r\n20 30\r\n40 30\r\n50 50\r\n70 10\r\n20 60\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2.000000\r\nCase 2: impossible\r\nCase 3: 2.895522\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}