06771. USACO·双符号猜拳 未做

注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。

在一局蹄子剪刀布游戏中，Bessie 和 Elsie 可以出 $N$ （$1\le N\le 3000$）种不同的蹄子手势，编号为 $1\dots N$，每个手势对应一种不同的材料。不同材料之间的相互关系有一个复杂的表格，基于该表格，可能会：

• 一种手势获胜，另一种失败。
• 两种手势平局。

蹄子剪刀布-1.0 的规则类似，但 Bessie 和 Elsie 可以各自出两个手势，每只蹄子出一个。在观察到她们所出的四个手势后，她们各自选择其中一个手势进行游戏。结果根据正常的蹄子剪刀布的规则决定。

给定 Elsie 计划在每局游戏中出的 $M$（$1\le M\le 3000$）个手势组合，Bessie 想知道有多少种不同的手势组合可以确保战胜 Elsie。一个手势组合定义为一个有序对 $(L,R)$，其中 $L$ 为奶牛用左蹄出的手势，$R$ 为奶牛用右蹄出的手势。你能为每局游戏进行计算吗？

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$，表示蹄子手势的数量，以及 Bessie 与 Elsie 进行的游戏局数。

以下 $N$ 行，第 $i$ 行由 $i$ 个字符 $a_{i,1}{a}_{i,2}\dots a_{i,i}$ 组成，其中 $a_{i,j}\in \{\text{D},\text{W},\text{L}\}$。如果 $a_{i,j}=\text{D}$，则手势 $i$ 平于手势 $j$。如果 $a_{i,j}=\text{W}$，则手势 $i$ 胜于手势 $j$。如果 $a_{i,j}=\text{L}$，则手势 $i$ 负于手势 $j$。输入保证 $a_{i,i}=\text{D}$。

以下 $M$ 行，每行包含两个空格分隔的整数 $s_1$ 和 $s_2$，其中 $1\le s_1,s_2\le N$，表示 Elsie 在该局游戏中的手势组合。

输出 $M$ 行，其中第 $i$ 行包含在第 $i$ 局游戏中 Bessie 可以确保战胜 Elsie 的手势组合数量。

【样例解释】

在这个例子中，这对应于原始的蹄子剪刀布，我们可以设蹄子为 1，布为 2，剪刀为 3。 布战胜蹄子，蹄子战胜剪刀，剪刀战胜布。Bessie 无法确保战胜蹄子+布或布+剪刀的组合。然而，如果 Elsie 出蹄子+蹄子，Bessie 可以采用以下任一组合进行反击。

• 布+布

• 布+剪刀

• 布+蹄子

• 蹄子+布

• 剪刀+布

如果 Bessie 出这些组合中的任意一个，她可以确保通过出布来获胜。

• 测试点 7-12：没有额外限制。

【数据规模与约定】

• 测试点 2-6：$N,M\le 100$。

• 测试点 7-12：没有额外限制。

供题：Suhas Nagar