Expected Hitting Time in a Random Walk on a Tree

ckw has an unrooted tree with n vertices. Some vertices are marked. Prior to beginning his walk, ckw arbitrarily chooses a starting vertex (i.e. uniformly at random among the n vertices). Then, at every unit time, he jumps with equal probability to any vertex whose distance from his current location is at most $$2$$ (that is, any vertex at distance $$0$$, $$1$$, or $$2$$). Note that if the current vertex is marked, the process stops immediately (with zero additional time).

For any unmarked vertex $$u$$, let $$S(u)$$ denote the set of vertices such that the distance from $$u$$ is no more than $$2$$. The expected time from an unmarked vertex satisfies the relation $$ E(u) = 1 + \frac{1}{|S(u)|} \sum_{v \in S(u)}E(v), $$ where for every marked vertex $$v$$, we define $$E(v)=0$$. Since ckw picks his starting vertex uniformly at random, the answer is the average expected time: $$\frac{1}{n}\sum_{u=1}^{n}E(u).$$

Your task is to compute this expected time given the tree and the marked vertices.

inputFormat

The input begins with a line containing two integers $$n$$ and $$m$$, where $$n$$ is the number of vertices in the tree (numbered from 1 to $$n$$) and $$m$$ is the number of marked vertices.

The following $$n-1$$ lines each contain two integers $$u$$ and $$v$$, representing an undirected edge connecting vertices $$u$$ and $$v$$.

The last line contains $$m$$ distinct integers indicating the marked vertices.

outputFormat

Output a single real number: the expected time for ckw to first reach a marked vertex. Your answer is accepted if its absolute or relative error does not exceed $$10^{-6}$$.

sample

3 1
1 2
2 3
3

2.000000