문제 번호 5057 --품종 가짓수(Breed Assignment)

5057: 품종 가짓수(Breed Assignment)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 7  해결 문제 수: 2
[제출][채점상황][게시판][:]

문제 설명

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

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

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


 

입력

Line 1 : 두 정수 NK가 주어진다.

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번 소가 다른 품종임을 나타낸다.

출력

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

입력예시

4 2
S 1 2
D 1 3

출력예시

18

도움말

출처

[제출][채점상황]