혼합용 그릇

점심을 만들기 위해 조리법을 따르고 있다.

이 조리법은 재료들을 그릇에 함께 넣어 만든 혼합물이다. 각 재료는 다음 중 하나이다.

• 먼저 별도의 그릇에서 만들어야 하는 또 다른 혼합물

• 주방에 이미 있어 바로 넣을 수 있는 기본 재료

혼합물을 만들려면 모든 재료를 준비하고 빈 그릇을 하나 가져와 그 안에서 재료들을 섞어야 한다. 그릇에 이미 들어 있는 혼합물에 재료를 추가하여 혼합물을 만드는 것은 불가능하다.

예를 들어, CAKE(혼합물)을 CAKEMIX(혼합물)과 거짓말(기본 재료)로 만들려면, 먼저 CAKEMIX을 별도의 그릇에서 만든 다음, 두 번째 그릇에 CAKEMIX과 거짓말을 넣어 CAKE을 만들어야 한다.

혼합물을 재료로 사용하여 그 혼합물을 준비했던 그릇을 비운 뒤에는 그 그릇을 다른 혼합물을 만드는 데 다시 사용할 수 있다. 따라서 조리법을 준비하는 데 필요한 그릇의 수는 혼합물을 만들기로 한 순서에 따라 달라진다.

필요한 그릇 수의 최솟값을 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ C ≤ 10 2 ≤ M ≤ 10

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 10

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000

첫 번째 줄에는 입력 파일의 테스트 케이스 수를 나타내는 정수 C가 주어진다.

각 테스트 케이스에는 다음이 주어진다.

• 테스트 케이스에 있는 혼합물의 수를 나타내는 정수 N이 담긴 한 줄

• 각 혼합물마다 하나씩 주어지는 N개의 줄. 각 줄에는 다음이 주어진다.

• 혼합물의 이름을 나타내는 하나의 문자열

• 이 혼합물에 들어가는 재료의 수를 나타내는 정수 M

• 이 혼합물에 들어가는 각 재료의 이름을 나타내는 M개의 문자열

한 줄의 토큰들은 하나의 공백으로 구분된다.

테스트 케이스의 첫 번째 혼합물이 만들려는 조리법이다.

혼합물의 이름은 1개 이상 20개 이하의 UPPERCASE 문자로 이루어진 문자열이다.

기본 재료의 이름은 1개 이상 20개 이하의 소문자로 이루어진 문자열이다.

조리법은 다른 어떤 혼합물에도 사용되지 않으며, 이를 제외한 각 혼합물은 정확히 하나의 다른 혼합물에 사용된다. 각 재료는 한 혼합물의 재료 목록에 최대 한 번만 등장한다. 어떤 혼합물도 직접적으로든 간접적으로든 자기 자신을 재료로 요구하지 않는다.

각 테스트 케이스마다 "Case #X: Y"을 한 줄에 출력한다. 이때 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 필요한 혼합용 그릇 수의 최솟값이다.

첫 번째 경우에는 SOUP에 대한 갈망을 충족하기 위해 다음 단계를 따른다.

• 그릇에서 셀러리와 양파를 섞어 VEGETABLES을 만든다.

• 두 번째 그릇에서 닭고기와 첫 번째 그릇의 VEGETABLES을 섞어 STOCK을 만든다. 첫 번째 그릇은 비게 된다.

• 첫 번째 그릇에서 STOCK, 소금, 물을 섞어 SOUP을 만든다.

두 번째 경우에는 MILKSHAKE을 만들기 위해 우유 및 아이스크림과 섞기 전에 FLAVOR과 FRUIT 중 어느 것을 먼저 만들지 선택할 수 있다.

FRUIT을 먼저 만들면 그릇 네 개를 사용한다.

• 그릇에서 바나나와 베리를 섞어 FRUIT을 만든다.

• 두 번째 그릇에서 육두구와 계피를 섞어 SPICES을 만들고, 세 번째 그릇에서 코코아와 시럽을 섞어 CHOCOLATE을 만든다. (어느 순서든 가능하다)

• 네 번째 그릇에서 SPICES과 CHOCOLATE을 섞어 FLAVOR을 만든다.

• 두 번째 또는 세 번째 그릇에서 FRUIT, FLAVOR, 우유, 아이스크림을 섞어 MILKSHAKE을 만든다.

하지만 FLAVOR 다음에 FRUIT을 만들면 그릇 세 개를 사용한다.

• 그릇에서 육두구와 계피를 섞어 SPICES을 만들고, 두 번째 그릇에서 코코아와 시럽을 섞어 CHOCOLATE을 만든다. (어느 순서든 가능하다)

• 세 번째 그릇에서 SPICES과 CHOCOLATE을 섞어 FLAVOR을 만든다.

• 첫 번째 그릇에서 바나나와 베리를 섞어 FRUIT을 만든다.

• 두 번째 그릇에서 FRUIT, FLAVOR, 우유, 아이스크림을 섞어 MILKSHAKE을 만든다.