蜗牛的房子遗失在了一棵树的某个叶子结点上，它要从根结点出发开始寻找它的房子。有一些中间结点可能会住着一些虫子，这些虫子会告诉蜗牛它的房子是否在以这个中间结点为根的子树上，这样蜗牛就不用白跑路了。当然，如果有些结点没有住着虫子的话，那么可怜的蜗牛只有靠自己决定访问顺序来探索了。假设蜗牛走过一条边的耗费都是 $1$，且房子遗失在每个叶子结点的概率都是相等的，那么请问蜗牛找到他的房子的最小数学期望值？

例如在下面的这棵树当中：

蜗牛从根结点 $1$ 出发开始寻找它的房子，它的房子可能遗失在 $2,4,5$。在结点 $3$ 上住着一只虫子，它会告诉蜗牛，以 $3$ 为根的子树上是否有蜗牛的房子。蜗牛有两种走法。蜗牛可以先访问 $2$，如果它在那儿不能找到房子，那么它要回到根结点 $1$，再通过 $3$ 来访问结点 $4$（或 $5$），如果还是不能找到它的房子，那么它又要回到结点 $3$，再去访问结点 $5$（或 $4$）。在这种走法中，当房子分别位于 $2,4,5$ 的时候，蜗牛需要走的步数分别是 $1,4,6$，期望值是 $\frac{1+4+6}{3}=\frac{11}{3}$。显然，这种走法没有充分发挥虫子在这里起到的作用。在另一种走法中，蜗牛先访问结点 $3$，它可以从住在 $3$ 上的虫子那里得知它的房子是否存在于 $4$ 或 $5$ 的信息。在这种走法中，当房子分别位于 $2,4,5$ 的时候，蜗牛需要走的步数分别是 $3,2,4$，期望值是 $\frac{3+2+4}{3}=3$。这种走法合理的利用了虫子提供的信息，得到了更优的数学期望值。

输入格式

输入包含多组测试数据。

每个数据以一行开始，其中包含一个整数 $n$，表示树中点的数量。然后按照 $n$ 行描述 $n$ 个点。为了方便起见，我们将所有的点从 $1$ 到 $n$ 编号。用 $1$ 编号的点总是树的根节点。这 $n$ 行中的第 $i$ 行用数字 $i$ 描述点。每行由一个整数和一个大写字符Y或N组成，用一个空格分隔，表示父亲的编号以及是否存在虫子（Y表示存在，而 N表示不存在）。一个点的父亲是指该点与编号为 $1$ 的点之间最短路径上的与该点相邻的点。在上图中，点 $2$ 或 $3$ 的父亲是点 $1$，而点 $4$ 或 $5$ 的父亲是点 $3$。对于父亲 $1$，此整数为 $-1$，表示它没有父亲。示例输入中的第一组描述了上图。

$n=0$ 的测试数据表示输入结束，不应进行处理。

输出格式

每组测试数据输出一行。

该行包含一个浮点数，小数点后保留四位数字，这是数学期望值。

样例

5
-1 N
1 N
1 Y
3 N
3 N
10
-1 N
1 Y
1 N
2 N
2 N
2 N
3 N
3 Y
8 N
8 N
6
-1 N
1 N
1 Y
1 N
3 N
3 N
0

3.0000
5.0000
3.5000

数据规模与约定

对于所有数据，$1\le n\le 1000$，$0\le k\le 8$。（$k$ 是每个节点的分叉数。）

题目来源

ACM BeiJing2004