가계도 1초 1024MB
문제
2025년 3월, 노을이 아름답던 어느 날. 수아는 도서관에서 빌려온 가계도들 위에 라면 국물을 엎질러버렸다. 수아는 급히 헤어드라이어를 동원해 가계도들을 말리긴 했지만... 불행히도, 인물들의 성별을 나타내던 수성 잉크가 전부 지워지고 말았다.
수아가 빌려온 가계도는 아래의 특징을 가지고 있다.
임의의 구성원의 성별은 남성이거나 여성이다.
각 구성원은 자신의 성별과 다른 성별의 사람과 결혼 할 수 있다.
어떠한 구성원
p 의 조상은 아래와 같이 귀납적으로 정의된다.p 의 부모는p 의 조상이다.p 의 부모의 조상 또한P 의 조상이다.
p 자신은p 의 조상이 아님에 유의하라.반대로 어떠한 구성원
p 의 후손은p 를 조상으로 가지는 구성원들이다.임의의 두 구성원
p 와q 에 대해,p 는q 의 조상이면서 후손일 수는 없다.
수아는 가계도를 복구하는 과정에서 위의 특징을 모두 만족하면 유효한 가계도라 하기로 하였다. 수아는 인물들의 성별을 하나하나 복구하기엔 너무 귀찮다고 생각하여, 각 구성원의 성별을 적절히 배정하여 유효한 가계도의 개수를 세어보기로 했다. 수아를 도와 유효한 가계도를 만드는 성별 배정의 총 가짓수를 구하는 프로그램을 작성해 보자.
입력
첫 번째 줄에 가계도에 등장하는 구성원의 수
두 번째 줄부터
출력
유효한 가계도를 성별 배정의 총 가짓수를 출력한다. 단, 값이 너무 커질 수 있으니
예제 #1
6 4
1 2 3
2 3 4
3 4 5
4 5 6
4
예제 #2
8 4
1 2 5
2 3 6
3 4 7
4 1 8
32
예제 #3
10 4
1 3 4
3 4 1
3 9 2
1 9 3
0
예제 #4
12 7
1 2 6
2 3 7
3 4 8
4 5 9
1 9 10
5 7 11
10 11 12
32
예제 #5
4 2
1 2 3
1 3 2
0
로그인해야 코드를 작성할 수 있어요.