웹 서비스 의존 관계

Docker는 분산 애플리케이션을 가벼운 컨테이너 형태로 만들고 배포하고 실행하는 오픈 플랫폼이다. 컨테이너는 사용자 모드에서 도는 가벼운 가상 머신이라고 보면 된다. Amazon의 EC2 Container Service(ECS)는 Docker 컨테이너로 태스크라는 상위 개념을 구성한다. 태스크는 컨테이너 하나 이상과 그 의존 관계로 이루어지고, ECS는 이 컨테이너를 올바른 순서로 띄운다. 어떤 컨테이너는 자신이 의존하는 컨테이너가 모두 이미 실행 중일 때만 띄울 수 있다. Amazon은 서로 다른 실행 순서마다 성능을 비교하려고 하므로, ECS는 유효한 실행 순서가 몇 가지인지 알아야 한다. 각 구성마다 그 개수를 구하라.

첫 줄에 구성의 개수 $N$ ($1 \le N \le 100$)이 주어진다.

각 구성의 첫 줄에는 컨테이너의 개수 $M$ ($1 \le M \le 12$)이 주어진다. 이어지는 $M$개의 줄에는 영숫자로 된 이름이 공백으로 구분되어 주어진다. 각 줄의 첫 이름은 컨테이너이고, 나머지 이름은 그 컨테이너가 의존하는 컨테이너이며 나열 순서는 정해져 있지 않다.

이름의 길이는 10자 이하이고 대소문자를 구별한다. $M$개의 컨테이너는 각각 정확히 한 줄의 첫 이름으로 나타나고, 의존 대상으로 적히는 이름은 모두 이 $M$개 중 하나다. 한 줄에 같은 의존 대상이 두 번 이상 적힐 수 있고, 자기 자신을 의존 대상으로 적을 수도 있다.

각 구성마다 Case #n: 을 출력한 다음, 유효한 실행 순서의 개수를 출력한다. 여기서 $n$은 1부터 시작하는 구성 번호다. 유효한 순서가 없으면 0을 출력한다.