시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 7 7 1 100.000%

문제

Docker is an open platform for developers to build, ship and run distributed applications in the form of lightweight containers. You may think of a container as a lightweight virtual machine that runs in user-mode. Amazon is building EC2 Container Service (ECS) that uses Docker containers to build a higher-level abstraction known as a Task. A Task consists of one or more containers and their dependencies and it is the job of ECS to launch the containers in the correct order. A container can only be launched if all the containers it depends upon are already running. For performance reasons Amazon is interested in trying out different valid orders for launching the containers. Your task is to help ECS find the number of valid orders for launching the containers.

입력

The input consists of multiple test cases. The first line of input is the number of test cases N (1≤N≤100). The first line of each test configuration contains an integer M (1≤M≤12) specifying the number of containers in that configuration. Each of the next M lines contains a space-separated list of alphanumeric container names and their dependencies. Each container name is at most 10 characters long. The first token is the container name and all subsequent tokens are its dependencies in an arbitrary order.

출력

For each test configuration in the input output “Case #n: ” where n is the test case number followed by the maximum number of boot-order sequences of the containers.

예제 입력

3
3
a b c
b c
c
6
c1 c2
c2 c3
c4 c5
c3 c5
c5 c6
c6
1
a a

예제 출력

Case #1: 1
Case #2: 4
Case #3: 0

힌트

출처

ACM-ICPC > Regionals > Asia > Pakistan > Asia Lahore Regional 2014 6번