测试数据来自 system/1962

描述

Alice设计了一个树结构，有N个结点（包括根）被依次编号为1到N，由N-1条边连接。后来，Bob在上面增加了K条原来没有的边（也就是说既不是自环，也不会因此产生重边）并称这样得到的图为“K-嫁接树”。

现在Alice希望对嫁接树的每一个结点进行染色，允许使用的颜色恰有N种，分别编号为1到N。Alice要求相邻两个结点要涂上不同的颜色。

假设颜色为i的结点有\(t_i\)个，则Bob给出了如下的评价分数：

\(score~=~\frac{t_1+\frac{t_2}{2}+\frac{t_3}{3}+\cdots +\frac{t_N}{N}}{1+P(t_1+2t_2+3t_3+\cdots +Nt_N)}\)

其中P为非负系数。现在，Alice希望可以找到一种染色方案，使得Bob给出来的评分最大。你能帮助他吗？

格式

输入格式

第一行有2个整数，依次为N和K，如题所述。

第二行到第N+K行，每行有两个整数u和v，依次给出了N+K-1条边。保证不存在自环，也不存在重边。

最后一行给定非负浮点数P。

输出格式

输出最大的可能评分，四舍五入保留到小数点后第三位。

样例1

样例输入1

9 0
1 2
1 3
1 4
1 5
2 6
2 7
2 8
2 9
2.5

样例输出1

0.253

限制

对于50%的数据，K=0，\(1\le N\le 100000\)，\(0\le P<10\)。其中有25%的数据P=0。

对于另外50%的数据，\(K\le 2\)，\(1\le N\le 20000\)，\(0\le P<10\)。其中也有25%的数据P=0。

来源

SDOI2015 round2 day2