描述

有一天，一只蜗牛爬到了一棵大树上，并最终来到了树枝的尽头。从这样一个从未到过的地方向下看，感觉真是大不相同！然而，由于长时间的攀爬，他非常疲惫，于是睡着了。当他醒来时，发生了一件令人难以置信的事情——他发现自己躺在一片草地上，而他原本背上的房子也消失了！他立刻意识到，自己在睡觉时从树枝上掉了下来！他确信他的房子一定还在他睡觉时所在的那根树枝上。蜗牛开始再次爬树，因为他无法没有房子而生活。

当到达树的第一个分叉点时，他悲伤地发现自己无法记起之前爬过的路线。为了找到他心爱的房子，蜗牛决定去每一个树枝的尽头。没有房子的保护而行走是危险的，所以他希望以最好的方式搜索这棵树。

幸运的是，树上住着许多热心的虫子，它们可以准确地告诉蜗牛，在他掉下来之前，他是否曾经经过它们所在的地方。

现在我们的工作是帮助这只蜗牛。我们最关注树的两个部分——树枝的分叉点和树枝的尽头，我们称它们为关键点，因为关键事件总是在那里发生，比如选择一条路径、得到虫子的帮助以及到达他正在寻找的房子。

假设所有的虫子都住在关键点上，两个相邻关键点之间的所有树枝的距离都是1。蜗牛现在在树的第一个分叉点。

我们的目标是找到一条合适的路线，通过分析树的结构和虫子的位置，让他尽快找到他的房子。对路线的唯一限制是，他必须在到达从这个分叉点长出的所有尽头之前，不能从一个分叉点向下走。

房子可能以相等的概率留在任何树枝的尽头。我们关注蜗牛在到达他的房子之前必须覆盖的距离的数学期望。我们希望这个值尽可能小。

如图1所示，蜗牛在关键点1，他的房子在2、4和5中的某个点。一只虫子住在点3，它可以告诉蜗牛他的房子是否在4和5中的一个点。因此，蜗牛可以选择两种策略。他可以先去点2。如果他没有在那里找到房子，他应该返回点1，然后通过点3到达点4（或5）。如果仍然没有找到，他必须返回点3，然后去点5（或4），他无疑会在那里找到他的房子。在这种选择中，蜗牛覆盖的距离分别为1、4、6，对应于房子分别位于点2、4（或5）、5（或4）的情况。因此，期望值为$(1 + 4 + 6) / 3 = 11 / 3$。显然，这种策略没有充分利用虫子的信息。如果蜗牛先去点3并从虫子那里获得有用的信息，然后选择返回点1然后前往点2，或者去点4或5碰碰运气，他覆盖的距离将分别为2、3、4，对应于房子的不同位置。在这种策略中，数学期望将是$(2 + 3 + 4) / 3 = 3$，这正是蜗牛应该搜索树的路线。

输入

输入包含多组测试数据。每组测试数据以一行包含一个整数$N$开始，$N$不超过1000，表示树中的关键点数量。然后是$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

来源

2004年北京