USACO 2013 March Bronze - Breed Assignment

FJ에게는 세 가지 다른 품종(Holstein, Jersey, Guernsey)의 소 N마리(2 <= N <= 15)가 있다.

불행하게도, FJ는 소들의 품종을 잊어버렸다! 다행히도 FJ는 소들 사이의 관계를 K(1 <= K <= 50)개 알고 있다. 예를 들어, 1번과 2번 소가 같은 품종이거나, 1번과 5번 소가 다른 품종인 것을 알고 있을 수도 있다.

이러한 관계가 입력으로 주어질 때, 소들의 가능한 품종의 가짓수를 구하는 프로그램을 만드시오.(입력된 정보가 모순일 때는 0을 출력한다.)

PROBLEM NAME : assign

INPUT FORMAT

Line 1 : 두 정수 N과 K가 주어진다.

Line 2~K+1 : x번 소와 y번 소의 관계를 나타내는 정보가 주어진다.(1 <= x, y <= N, x != y) 입력은 “S x y”나 “D x y”로 주어지는데, “S x y”는 x번 소와 y번 소가 같은 품종임을 나타내고, “D x y”는 x번 소와 y번 소가 다른 품종임을 나타낸다.

OUTPUT FORMAT

Line 1 : 소들의 가능한 품종의 가짓수를 출력한다.

SAMPLE INPUT

4 2 S 1 2 D 1 3

SAMPLE OUTPUT

18

http://www.usaco.org/index.php?page=viewproblem2&cpid=261