Given a tree with \(N\) nodes and \(N - 1\) edges rooted at node \(1\). You have to answer \(Q\) queries. In every query, you will be given a node \(x\).
Alice will tell his friend Bob the distance from \(1\) to \(x\). But Bob only knows how to reach a particular distance from \(1\). Find the probability that Bob will reach \(x\) in one try. If \(P\) will be the probability then print \(\frac{1}{P}\) in each query.
Note - The distance between two vertices in a tree is equal to the number of edges on the unique simple path between them.
Input Format
- The first line contains \(N\) and \(Q\) — number of nodes and queries.
- The next \(N-1\) lines follow. The \(i^{th}\) line contains two integers \(X_i, Y_i\) denoting an edge between the nodes \(X_i,Y_i\). It is guaranteed that the given nodes and edges form a tree.
- The next \(Q\) lines contain a node \(x\).
Output Format
For each query, If \(P\) will be the probability to reach \(x\) in one try then print \(\frac{1}{P}\) in a separate line.
Constraints
\(1 \leq N, Q \leq 10^5 \\ 1 \leq X_i, Y_i \leq N \\ X_i \neq Y_i \\ 1 \leq x \leq N\)