Breed Assignment

Farmer John has $N$ cows ($2 \le N \le 15$), each of one of three breeds: Holstein, Jersey, or Guernsey.

Unfortunately, Farmer John cannot remember the exact breed of each cow. He does, however, remember a list of $K$ ($1 \le K \le 50$) relationships between pairs of cows. For example, he might remember that cows 1 and 2 have the same breed, or that cows 1 and 5 have different breeds.

Given Farmer John's list of relationships between pairs of cows, compute the number of different possible assignments of breeds to his cows. (This number can be $0$ if the list contains contradictory information.)

• Line 1: Two space-separated integers $N$ and $K$.
• Lines 2 through $K+1$: Each line describes the relationship between two cows $x$ and $y$ ($1 \le x, y \le N$, $x \ne y$). It is either of the form S x y, meaning $x$ and $y$ have the same breed, or D x y, meaning $x$ and $y$ have different breeds.

• Line 1: The number of possible breed assignments.

For example, suppose there are $4$ cows where cows 1 and 2 have the same breed and cows 1 and 3 have different breeds. The first three cows admit six possible assignments: HHG, HHJ, GGH, GGJ, JJH, JJG. For each of them the fourth cow is unconstrained and may take any of the three breeds, giving $6 \times 3 = 18$ assignments consistent with Farmer John's list.