레이팅 미적용설명
농부 존(Farmer John)에게는 N마리 (2 <= N <= 15)의 소가 있으며, 각 소는 홀스타인, 저지, 건지 세 품종 중 하나이다.
안타깝게도 FJ는 소들의 정확한 품종을 기억하지 못한다! 하지만 소 쌍 사이의 K개 (1 <= K <= 50)의 관계 목록은 기억하고 있다. 예를 들어 소 1과 2가 같은 품종이라거나, 소 1과 5가 다른 품종이라는 것을 기억할 수 있다.
소 쌍 사이의 관계에 대한 FJ의 목록이 주어질 때, 소들에 품종을 배정하는 서로 다른 가능한 방법의 수를 계산하는 것을 도와주자 (목록에 모순된 정보가 있으면 이 수는 0일 수도 있다).
제약
입력 형식
첫째 줄: 공백으로 구분된 두 정수 N과 K.
둘째 줄부터 1+K번째 줄까지: 각 줄은 소 x와 y (1 <= x,y <= N, x != y) 쌍 사이의 관계를 설명한다. x와 y가 같은 품종이라는 뜻의 "S x y" 또는 x와 y가 다른 품종이라는 뜻의 "D x y" 형태이다.
출력 형식
가능한 품종 배정의 수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
assign.in · 출력을 쓸 파일 assign.out예제 1
입력
4 2
S 1 2
D 1 3출력
18설명
Output details: Six assignments are possible for the first 3 cows (HHG, HHJ, GGH, GGJ, JJH, JJG); for each, the 4th cow has 3 options, giving 18 total.
문제 정보
태그