tic-tac-toe 游戏在 $$$n$$$ 个顶点的树上开始。一些顶点已被着色为白色,而其余顶点则未着色。
有两名玩家——白人和黑人。玩家交替进行动作。白人玩家开始游戏。轮到他时,玩家必须选择一个未着色的顶点并将其涂成自己的颜色。
如果玩家用自己的颜色绘制了包含三个顶点的路径,则玩家获胜。如果所有顶点都被着色并且没有玩家获胜,则游戏以平局结束。
假设双方都发挥最佳状态,您能否找出谁将赢得比赛,或者是否以平局结束?
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 50\,000$$$) — 测试用例的数量。然后是 $$$T$$$ 测试用例的描述。
每个测试的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 树中的顶点数。
以下 $$$n - 1$$$ 行中的每一行都包含整数 $$$v$$$、$$$u$$$ ($$$1 \le v, u \le n$$$) 表示连接顶点 $$$v$$$ 和 $$$u$$$ 的树的边。
测试用例的最后一行包含一串字母“W”(表示白色)和“N”(表示未着色),长度为 $$$n$$$ 表示已经着色的顶点。已经涂成白色的顶点表示为“W”。
保证给定的边形成一棵树,至少有一个无色顶点,并且不存在三个白色顶点的路径。
保证所有测试用例中所有 $$$n$$$ 的总和最多为 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,根据游戏结果打印“White”、“Draw”或“Black”。
示例
输入 #1
2 4 1 2 1 3 1 4 NNNW 5 1 2 2 3 3 4 4 5 NNNNN
输出 #1
White Draw
注意
在第一个示例中,顶点 $$$4$$$ 已着色为白色。白色玩家可以通过首先将顶点 $$$1$$$ 涂成白色并在第二回合将剩余顶点涂成白色来获胜。该过程如下图所示。
在第二个示例中,我们可以证明没有玩家可以强制取得胜利。