The input contains several sets of test data. Each set begins with a line containing one integer N, no more than 1000, which indicates the number of key points in the tree. Then follow N lines describing the N key points. For convenience, we number all the key points from 1 to N. The key point numbered with 1 is always the first fork of the tree. Other numbers may be any key points in the tree except the first fork. The i-th line in these N lines describes the key point with number i. Each line consists of one integer and one uppercase character 'Y' or 'N' separated by a single space, which represents the number of the previous key point and whether there lives a worm ('Y' means lives and 'N' means not). The previous key point means the neighboring key point in the shortest path between this key point and the key point numbered 1. In the above illustration, the previous key point of point 2 or 3 is point 1, while the previous key point of point 4 or 5 is point 3. This integer is -1 for the key point 1, means it has no previous key point. You can assume a fork has at most eight branches. The first set in the sample input describes the above illustration.
A test case of N = 0 indicates the end of input, and should not be processed.
BZPRO
蜗牛从根结点1出发开始寻找它的房子，它的房子可能遗失在2、4、5。在结点3上住着一只虫子，它会告诉蜗牛，以3为根的子树上是否有蜗牛的房子。蜗牛有两种走法。蜗牛可以先访问2，如果它在那儿不能找到房子，那么它要回到根结点1，再通过3来访问结点4（或5），如果还是不能找到它的房子，那么它又要回到结点3，再去访问结点5（或4）。在这种走法中，当房子分别位于2、4、5的时候，蜗牛需要走的步数分别是1、4、6，期望值是(1+4+6)/3=11/3。显然，这种走法没有充分发挥虫子在这里起到的作用。在另一种走法中，蜗牛先访问结点3，它可以从住在3上的虫子那里得知它的房子是否存在于4或5的信息。在这种走法中，当房子分别位于2、4、5的时候，蜗牛需要走的步数分别是3、2、4，期望值是(3+2+4)/3=3。这种走法合理的利用了虫子提供的信息，得到了更优的数学期望值。