1418: #6171. 记忆的轮廓

Memory Limit:512 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

通往贤者之塔的路上,有许多的危机。

我们可以把这个地形看做是一颗树,根节点编号为 111 ,目标节点编号为 nnn ,其中 111nnn 的简单路径上,编号依次递增,在 [1,n][1,n][1,n] 中,一共有 nnn 个节点。 我们把编号在 [1,n][1,n][1,n] 的叫做正确节点, [n+1,m][n+1,m][n+1,m] 的叫做错误节点。一个叶子,如果是正确节点则为正确叶子,否则称为错误叶子。

莎缇拉要帮助昴到达贤者之塔,因此现在面临着存档位置设定的问题。为了让昴成长为英雄,因此一共只有 ppp 次存档的机会,其中 111nnn 必须存档。被莎缇拉设置为要存档的节点称为存档位置。

当然不能让昴陷入死循环,所以存档只能在正确节点上进行,而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气,因此莎缇拉假设昴每次位于树上一个节点时,都会等概率选择一个儿子走下去。每当走到一个错误叶子时,再走一步就会读档。

具体的,每次昴到达一个新的存档位置,存档点便会更新为这个位置(假如现在的存档点是 iii ,现在走到了一个存档位置 j>ij \gt ij>i ,那么存档点便会更新为 jjj )。读档的意思就是回到当前存档点。

初始昴位于 111 ,当昴走到正确叶子 nnn 时,便结束了路程。莎缇拉想知道,最优情况下,昴结束路程的期望步数是多少?

输入格式

第一行一个正整数 TTT 表示数据组数。
接下来每组数据,首先读入三个正整数 nnn , mmm , ppp
接下来 m−nm-nmn 行,描述树上所有的非正确边(正确边即连接两个正确节点的边),用两个正整数 j,kj,kj,k 表示 jjjkkk 之间有一条连边, jjjkkk 可以均为错误节点,也可以一个为正确节点另一个为错误节点。数据保证 jjjkkk 的父亲。

输出格式

TTT 行,每行一个实数表示每组数据的答案。请保留四位小数。

样例

样例输入

1
3 7 2
1 4
2 5
3 6
3 7

样例输出

9.0000

数据范围与提示

对于 100%100\%100% 的数据, 50≤p≤n50 \leq p \leq n50pnm≤1500m \leq 1500m1500T≤5T \leq 5T5

子任务 分值 nnn 特殊约定
1 50 n≤500n \leq 500n500 n=pn=pn=p
2 20
3 30 n≤700n \leq 700n700