题目描述

你的国家拥有若干个军队单位。除此之外还有若干个国家，每个国家要么是敌国，要么是中立国，并且各自拥有一定数量的军队单位。

一场战争由若干轮战斗组成。一旦你向某个相邻国家发动战争，战争会一直持续到其中一方的军队单位数变为 $0$。如果你击败了另一个国家，它的领土会并入你的领土，此后你可以向与当前任意已占领领土相邻的国家发动战争。

设一次战争中，你方当前有 $a$ 个军队单位，对方有 $b$ 个军队单位。在每一轮战斗中，恰好有一方损失一个单位。对方损失一个单位的概率为

$$\frac{a^2}{a^2+ab+b^2},$$

否则由你方损失一个单位。这里的 $a,b$ 都是在该轮战斗开始时双方当前拥有的单位数。

你的目标是击败所有敌国。中立国不要求必须击败，但有时为了到达某些敌国，可能必须先占领中立国。

每个国家用一行描述，格式为

type units borders

其中：

• type 为 Y、E 或 N，分别表示你的国家、敌国和中立国；
• units 表示该国初始拥有的军队单位数；
• borders 是若干个以空格分隔的国家编号，表示与该国相邻的国家，国家编号从 $0$ 开始。

你可以根据当前局面选择下一次进攻的国家。求采用最优进攻顺序时，在你方军队没有全部损失之前击败所有敌国的最大概率。

输入格式

第一行一个整数 $n$，表示国家数量。

接下来 $n$ 行，第 $i$ 行按照上述格式描述编号为 $i-1$ 的国家。若某个国家没有相邻国家，该行只包含 type units。

输出格式

输出一个实数，表示击败所有敌国的最大概率。

答案的绝对误差或相对误差不超过 $10^{-9}$ 即可。

数据范围

• $1\le n\le 15$；
• 恰有一个国家的 type 为 Y；
• type 只可能为 Y、E、N；
• $1\le units\le 20$；
• 所有相邻国家编号均在 $[0,n-1]$ 内；
• 同一行的相邻国家编号互不相同；
• 相邻关系保证对称：若 $a$ 与 $b$ 相邻，则 $b$ 与 $a$ 也相邻；
• 相邻关系不保证构成平面图，也不保证整张图连通。

样例 1

输入

2
Y 1 1
E 1 0

输出

0.3333333333333333

解释

双方都只有一个军队单位。敌方在第一轮损失单位的概率为 $1/(1+1+1)=1/3$。

样例 2

输入

2
Y 2 1
E 1 0

输出

0.7142857142857142

样例 3

输入

3
Y 1 1
E 1 0 2
N 1 1

输出

0.3333333333333333

样例 4

输入

3
Y 1 1
N 1 0 2
E 1 1

输出

0.1111111111111111

样例 5

输入

3
Y 2 1 2
E 2 0 2
E 1 0 1

输出

0.16250944822373392

样例 6

输入

2
Y 1
E 1

输出

0.0

样例 7

输入

1
Y 1

输出

1.0