Phân Giống Bò

Có $N$ con bò và 3 giống: Holstein (H), Jersey (J), Guernsey (G). Mỗi con bò thuộc đúng một giống. Cho $K$ quan hệ giữa các cặp bò:

• S x y: bò $x$ và bò $y$ cùng giống
• D x y: bò $x$ và bò $y$ khác giống nhau

Hãy đếm số cách phân giống cho $N$ con bò thỏa mãn tất cả $K$ quan hệ.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $K$
• $K$ dòng tiếp theo: Mỗi dòng là "S x y" hoặc "D x y" ($1\le x,y\le N$, $x\ne y$)

Dữ liệu ra

Một số nguyên: tổng số cách phân giống hợp lệ.

Ràng buộc

• $2\le N\le 15$
• $1\le K\le 50$

Ví dụ