在 Berland，有 $n$ 个城市和 $n - 1$ 条不同的双向道路连接着这些城市。城市编号从 $1$ 到 $n$，且任意两个城市之间都有路径相连（因此，Berland 可以被视为一棵树）。

当一名游客从其他国家飞抵城市 $u$ 并想要前往城市 $v$ 时，他会重复以下过程，直到到达城市 $v$：游客选择一个邻近城市（即与当前所在城市有道路直接相连的城市）并移动过去。在相邻城市之间通过每条道路都需要花费正好一小时。由于 Berland 没有路标，游客不知道该往哪里走，因此他每次随机选择一个邻居，且所有邻居被选中的概率相等。注意，游客不会记住之前走过的路，因此他可以选择刚刚到达该城市时所经过的那条路，也可以选择其他任何道路。

Berland 的国王关心游客平均花费的时间，所以他想知道对于某些给定的起点 $u_i$ 和终点 $v_i$，从 $u_i$ 出发到达 $v_i$ 平均需要多长时间。请回答他的问题。

输入格式

第一行包含一个整数 $n$，表示 Berland 的城市数量（$1 \le n \le 10^5$）。

接下来的 $n - 1$ 行描述道路，每行包含一对整数 $a_i, b_i$（$1 \le a_i, b_i \le n, a_i \neq b_i$），表示 $a_i$ 和 $b_i$ 之间有一条道路。保证给定的图是一棵树。

接下来一行包含一个整数 $q$，表示询问的数量（$1 \le q \le 2 \cdot 10^5$）。

接下来的 $q$ 行描述国王的询问：第 $i$ 行包含两个空格分隔的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$）。

输出格式

对于每个询问，输出游客从 $u_i$ 到达 $v_i$ 平均花费的时间（以小时为单位）。如果答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

样例

输入 1

3
1 2
2 3
3
1 2
2 1
3 3

输出 1

1.000000
3.000000
0.000000