Kéo Búa Bao Trừ Một

Trong trò chơi Kéo Búa Bao biến thể, có $N$ ký hiệu được đánh số từ $1$ đến $N$. Kết quả giữa hai ký hiệu được cho bởi một bảng: nếu ký hiệu $i$ đấu với ký hiệu $j$, kết quả là W (thắng), L (thua), hoặc D (hòa) từ góc nhìn của ký hiệu $i$.

Bessie và Elsie chơi $M$ ván. Trong mỗi ván, Elsie chọn hai ký hiệu $x$ và $y$ (công khai). Bessie sau đó chọn hai ký hiệu $a$ và $b$ (có thể trùng nhau). Cả hai người đều chọn một ký hiệu từ cặp của mình để đấu. Bessie thắng nếu cô ấy có ít nhất một ký hiệu đánh bại được cả hai ký hiệu của Elsie (bất kể Elsie chọn ký hiệu nào).

Đếm số cặp $(a,b)$ mà Bessie có thể chọn để đảm bảo thắng.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$.
• $N$ dòng tiếp theo: Dòng thứ $i$ chứa $i$ ký tự thuộc $\{D,W,L\}$ — kết quả khi ký hiệu $i$ đấu với ký hiệu $1,2,\dots ,i$.
• $M$ dòng tiếp theo: Hai số nguyên $x$, $y$ — cặp ký hiệu của Elsie.

Dữ liệu ra

• $M$ dòng, mỗi dòng là số cặp $(a,b)$ giúp Bessie thắng.

Ràng buộc

• $1\le N\le 3000$
• $1\le M\le 3000$
• Giới hạn thời gian: 3 giây

Ví dụ