Maximize Evaluation Score in K-Grafted Tree Coloring

Alice designed a tree structure with \(N\) nodes (including the root) numbered from \(1\) to \(N\) and connected by \(N-1\) edges. Later, Bob added \(K\) extra edges (which were not originally present, i.e. no self‐loops nor multiple edges are introduced) and called the resulting graph a K-grafted tree.

Alice now wants to color every node of this grafted tree. There are exactly \(N\) available colors, numbered from \(1\) to \(N\). The only restriction is that any two adjacent nodes must be colored with different colors. Suppose that the number of nodes painted with color \(i\) is \(t_i\), then Bob evaluates the coloring with the following score:

[ \mathit{score}=\frac{\displaystyle t_1+\frac{1}{2} t_2+\frac{1}{3} t_3+\cdots+\frac{1}{N} t_N}{\displaystyle 1+P \times\Bigl(t_1+2t_2+3t_3+\cdots+Nt_N\Bigr)} ]

Here, \(P\) is a nonnegative coefficient. Alice wants to choose a coloring scheme that maximizes Bob’s evaluation score. Can you help her?

Note: Although there are \(N\) colors available, you do not need to use all of them. You only need to produce a valid proper coloring (i.e. for every edge the two endpoints have different colors) whose induced counts \(t_i\) maximize the score defined above.

inputFormat

The input begins with a line containing three numbers: \(N\) \(K\) \(P\), where \(N\) is the number of nodes, \(K\) is the number of extra edges, and \(P\) is the coefficient used in the score evaluation. The next \(N-1\) lines each contain two integers \(u\) and \(v\), denoting an edge of the original tree. The following \(K\) lines each contain two integers \(u\) and \(v\), representing an extra edge added by Bob.

You may assume that \(N\) is small (e.g. \(N \le 10\)) so that an exhaustive search over all valid colorings is feasible.

outputFormat

Output a single line containing the maximum score achievable by a proper coloring of the grafted tree. The answer should be printed as a floating–point number with 6 decimal places.

sample

3 0 1
1 2
2 3

0.500000