CF629E.Famil Door and Roads

Famil Door’s City map looks like a tree (undirected connected acyclic graph) so other people call it Treeland. There are n intersections in the city connected by n - 1 bidirectional roads.

There are m friends of Famil Door living in the city. The i-th friend lives at the intersection u__i and works at the intersection v__i. Everyone in the city is unhappy because there is exactly one simple path between their home and work.

Famil Door plans to construct exactly one new road and he will randomly choose one among n·(n - 1) / 2 possibilities. Note, that he may even build a new road between two cities that are already connected by one.

He knows, that each of his friends will become happy, if after Famil Door constructs a new road there is a path from this friend home to work and back that doesn't visit the same road twice. Formally, there is a simple cycle containing both u__i and v__i.

Moreover, if the friend becomes happy, his pleasure is equal to the length of such path (it's easy to see that it's unique). For each of his friends Famil Door wants to know his expected pleasure, that is the expected length of the cycle containing both u__i and v__i if we consider only cases when such a cycle exists.

Famil Door 所在城市的地图是一棵树（即无向、连通、无环图），因此其他人称其为“树国”（Treeland）。城市中共有 $n$ 个交叉路口，由 $n-1$ 条双向道路连接。

城市中住着 Famil Door 的 $m$ 位朋友。第 $i$ 位朋友住在交叉路口 $u_i$，工作地点在交叉路口 $v_i$。由于任意两个路口之间恰好存在唯一一条简单路径，因此城中所有人都感到不开心。

Famil Door 计划恰好修建一条新道路，且他将从全部 $\frac{n\cdot(n-1)}{2}$ 种可能的无序路口对中随机均匀选择一个来修建（注意：他甚至可能在两个已经直接相连的路口之间再建一条新路）。

Famil Door 知道，当新道路建成后，若某位朋友能从家到公司再返回、且往返路径中不重复经过同一条边，则该朋友便会变得开心。形式化地说，即存在一个同时包含 $u_i$ 和 $v_i$ 的简单环。

此外，若该朋友变得开心，则他的愉悦值等于该环的长度（容易验证：此时满足条件的环是唯一的）。对于每一位朋友，Famil Door 想要知道他的期望愉悦值，即：在所有能使包含 $u_i$ 和 $v_i$ 的简单环存在的新道路修建方案中，该环长度的数学期望值。

The first line of the input contains integers n and m (2 ≤ n,  m ≤ 100 000) — the number of the intersections in the Treeland and the number of Famil Door's friends.

Then follow n - 1 lines describing bidirectional roads. Each of them contains two integers a__i and b__i (1 ≤ a__i, b__i ≤ n) — the indices of intersections connected by the i-th road.

Last m lines of the input describe Famil Door's friends. The i-th of these lines contain two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — indices of intersections where the i-th friend lives and works.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 100\,000$）—— 分别表示 Treeland 中的交叉路口数量以及 Famil Door 的朋友数量。

接下来 $n-1$ 行描述双向道路。每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$）—— 表示第 $i$ 条道路所连接的两个交叉路口的编号。

输入的最后 $m$ 行描述 Famil Door 的朋友们。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$）—— 分别表示第 $i$ 位朋友居住和工作的交叉路口编号。

For each friend you should print the expected value of pleasure if he will be happy. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

对于每位朋友，你需要输出他感到开心时的愉悦值的期望值。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的答案为 $b$。当满足 时，评测程序将判定你的答案正确。

Consider the second sample.

1. Both roads (1, 2) and (2, 3) work, so the expected length if
2. Roads (1, 3) and (2, 3) make the second friend happy. Same as for friend 1 the answer is 2.5
3. The only way to make the third friend happy is to add road (2, 3), so the answer is 3

考虑第二个样例。

1. 道路 $(1, 2)$ 和 $(2, 3)$ 均可用，因此期望长度为
2. 道路 $(1, 3)$ 和 $(2, 3)$ 可使第二位朋友满意。与第一位朋友的情况相同，答案为 $2.5$。
3. 唯一能使第三位朋友满意的方式是添加道路 $(2, 3)$，因此答案为 $3$。