Momiji 有一棵有根树,由 n 个节点组成。树节点由 1 到 n 的整数编号。根的编号是 1。红叶决定在这棵树上玩一个游戏。
游戏由几个步骤组成。在每一步中,Momiji 选择剩余的树节点之一(我们将其表示为 v),并从树中删除所有根位于节点 v 的子树节点。节点 v 也被删除。当树没有剩余节点时游戏结束。换句话说,游戏在选择节点号1的步骤之后结束。
每次 Momiji 在所有剩余节点中统一选择一个新节点。您的任务是找到所描述的游戏中步数的期望。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 树中的节点数。接下来的 n - 1 行包含树的边缘。第 i 行包含整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 由第 i 条边连接的节点的数量。
保证给定的图是一棵树。
输出
打印一个实数——所描述游戏中步数的期望。
如果绝对或相对误差不超过 10 - 6,则答案将被视为正确。
示例
输入 #1
2 1 2
输出 #1
1.50000000000000000000
输入 #2
3 1 2 1 3
输出 #2
2.00000000000000000000
注意
在第一个示例中,有两种情况。一种是直接去根,另一种是一步一步去根。因此预期的步骤是:
1 × (1 / 2) + 2 × (1 / 2) = 1.5
在第二个示例中,事情变得更加复杂。有两种情况减少到第一个样品,一种情况立即清洁。因此预期的步骤是:
1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2