#4899. 记忆的轮廓

题目描述

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

我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为$n$，其中$1$-$n$的简单路径上，编号依次递增，在$[1,n]$中，一共有$n$个节点。我们把编号在$[1,n]$的叫做正确节点，$[n+1,m]$的叫做错误节点。一个叶子，如果是正确节点则为正确叶子，否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。

为了让昴成长为英雄，因此一共有$p$次存档的机会，其中$1$和$n$必须存档。被莎缇拉设置为要存档的节点称为存档位置。当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气，因此莎缇拉假设昴每次位于树上某一个节点时，都会等概率选择一个儿子走下去。每当走到一个错误叶子时，再走一步就会读档。具体的，每次昴到达一个新的存档位置，存档点便会更新为这个位置（假如现在的存档点是$i$，现在走到了一个存档位置$j>i$，那么存档点便会更新为$j$）。读档的意思就是回到当前存档点。初始昴位于$1$，当昴走到正确节点$n$时，便结束了路程。莎缇拉想知道，最优情况下，昴结束路程的期望步数是多少？

输入格式

第一行一个正整数$T$表示数据组数。

接下来每组数据，首先读入三个正整数$n,m,p$。

接下来$m-n$行，描述树上所有的非正确边（正确边即连接两个正确节点的边）

用两个正整数$j,k$表示$j$与$k$之间有一条连边，$j$和$k$可以均为错误节点，也可以一个为正确节点另一个为错误节点。

数据保证$j$是$k$的父亲。

$50 \le p \le n \le 700$，$m \le 1500$，$T \le 5$。

数据保证每个正确节点均有至少2个儿子，至多3个儿子。

输出格式

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

样例

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

9.0000

数据范围与提示