本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

注意：本题时间限制为 3s，是默认时间限制的 1.5 倍。 在 Hoof Paper Scissors 的游戏中，Bessie 和 Elsie 可以出 $N$ （$1 \leq N \leq 3000$）种不同的蹄部符号之一，标号为 $1\dots N$，每种符号对应一种不同的材料。不同材料之间如何相互作用由一张复杂的表决定，并且根据该表，有以下三种结果之一： 某个符号获胜，另一个符号失败。 两个符号平局。 Hoof Paper Scissors Minus One 的规则类似，只是 Bessie 和 Elsie 每人可以同时出两个符号（每只蹄子一个）。在观察到四个符号全部出完之后，她们各自从自己的两个符号中选择一个来出。胜负按照普通 Hoof Paper Scissors 的规则决定。 给定 Elsie 在每局游戏中计划使用的 $M$（$1 \leq M \leq 3000$）种符号组合，Bessie 想知道有多少种不同的符号组合能够保证战胜 Elsie。一个符号组合被定义为有序对 $(L,R)$，其中 $L$ 是奶牛左蹄出的符号，$R$ 是奶牛右蹄出的符号。你能为每局游戏计算这一数值吗？

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$，分别表示蹄部符号的数量，以及 Bessie 和 Elsie 进行的游戏局数。 接下来 $N$ 行输入中，第 $i$ 行由 $i$ 个字符 $a_{i,1}a_{i,2}\ldots a_{i,i}$ 组成，其中每个 $a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}$。如果 $a_{i,j} = \texttt D$，则符号 $i$ 与符号 $j$ 平局。如果 $a_{i,j} = \texttt W$，则符号 $i$ 战胜符号 $j$。如果 $a_{i,j} = \texttt L$，则符号 $i$ 输给 符号 $j$。保证 $a_{i,i} = \texttt D$。 接下来 $M$ 行每行包含两个用空格分隔的整数 $s_1$ 和 $s_2$，其中 $1 \leq s_1,s_2 \leq N$。这表示 Elsie 在该局游戏中的符号组合。

输出格式

输出 $M$ 行，其中第 $i$ 行包含能够保证 Bessie 在第 $i$ 局游戏中战胜 Elsie 的符号组合数量。

3 3
D
WD
LWD
1 2
2 3
1 1

0
0
5

提示

在本例中，这对应于原始的 Hoof Paper Scissors 并且我们可以令 Hoof=1、Paper=2、Scissors=3。Paper 胜 Hoof，Hoof 胜 Scissors，Scissors 胜 Paper。Bessie 无法保证在 Hoof+Paper 或 Paper+Scissors 这两种组合下获胜。 然而，如果 Elsie 出 Hoof+Hoof，Bessie 可以用下列任意组合进行反制。 Paper+Paper Paper+Scissors Paper+Hoof Hoof+Paper Scissors+Paper 如果 Bessie 出上述任意一种组合，她都可以通过选择出 Paper 来保证获胜。 SCORING: Inputs 2-6: $N,M\le 100$ Inputs 7-12: No additional constraints. Problem credits: Suhas Nagar

来源

USACO|2025|Bronze