알러지가 심한 친구들
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- ALLERGY
- 5000ms
- 65536kb
- 6347
- 1215 (19%)
-
- 출처
- 분류
문제
집들이에 n 명의 친구를 초대하려고 합니다. 할 줄 아는 m 가지의 음식 중 무엇을 대접해야 할까를 고민하는데, 친구들은 각각 알러지 때문에 못 먹는 음식들이 있어서 아무 음식이나 해서는 안 됩니다. 만들 줄 아는 음식의 목록과, 해당 음식을 못 먹는 친구들의 목록이 다음과 같은 형태로 주어진다고 합시다.
친구 | 갈비찜 | 피자 | 잡채 | 떡볶이 | 탕수육 | 닭강정 |
---|---|---|---|---|---|---|
채린 | x | o | o | o | x | x |
봄 | x | x | x | x | o | o |
다라 | o | x | o | x | o | x |
민지 | o | o | x | x | x | o |
각 친구가 먹을 수 있는 음식이 최소한 하나씩은 있도록 하려면 최소 몇 가지의 음식을 해야 할까요? 위 경우라면 다 같이 먹을 수 있는 음식이 없기 때문에 결국 두 가지 이상 음식을 해야 합니다. 피자와 탕수육, 혹은 잡채와 닭강정처럼 두 개 이상의 음식을 선택해야만 모두가 음식을 먹을 수 있지요. 친구들의 정보가 주어질 때 최소한 만들어야 하는 요리의 가지수를 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 T (T <= 50 ) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 친구의 수 n (1 <= n <= 50) 과 할 줄 아는 음식의 수 m (1 <= m <= 50) 이 주어집니다. 다음 줄에는 n 개의 문자열로 각 친구의 이름이 주어집니다. 친구의 이름은 10 자 이하의 알파벳 소문자로만 구성된 문자열입니다. 그 후 m 줄에 하나씩 각 음식에 대한 정보가 주어집니다. 각 음식에 대한 정보는 해당 음식을 먹을 수 있는 친구의 수와 각 친구의 이름으로 주어집니다.
모든 친구는 하나 이상의 음식을 먹을 수 있다고 가정해도 좋습니다.
출력
각 테스트 케이스마다 한 줄에 만들어야 할 최소의 음식 수를 출력합니다.
예제 입력
2 4 6 cl bom dara minzy 2 dara minzy 2 cl minzy 2 cl dara 1 cl 2 bom dara 2 bom minzy 10 7 a b c d e f g h i j 6 a c d h i j 3 a d i 7 a c f g h i j 3 b d g 5 b c f h i 4 b e g j 5 b c g h i
예제 출력
2 3
노트