문제
지루한 쉘 게임을 하는 것에 지친 베시와 그녀의 친구 엘시는 "동물 맞추기"라는 또 다른 흔한 게임을 즐깁니다.
처음에 베시는 어떤 동물을 생각합니다 (대부분 이 동물은 소인데, 게임이 꽤 지루해지지만, 가끔 베시는 창의적으로 다른 동물을 생각합니다). 그런 다음 엘시는 그 동물이 무엇인지 알아내기 위해 일련의 질문을 합니다. 각 질문은 동물이 특정 특성을 가지고 있는지 묻는 질문이며, 베시는 각 질문에 "네" 또는 "아니요"로 대답합니다. 예를 들면:
엘시: "그 동물은 날 수 있나요?"
베시: "아니요"
엘시: "그 동물은 풀을 먹나요?"
베시: "네"
엘시: "그 동물은 우유를 생산하나요?"
베시: "네"
엘시: "그 동물은 '음매' 소리를 내나요?"
베시: "네"
엘시: "그렇다면 그 동물은 소인 것 같아요."
베시: "맞아요!"
"가능한 집합(feasible set)"을 엘시가 지금까지 한 질문과 일치하는 특성을 가진 모든 동물들의 집합이라고 한다면, 엘시는 가능한 집합에 동물이 하나만 남을 때까지 계속 질문을 합니다. 그 후에 그 동물이 무엇인지 발표합니다. 각 질문에서 엘시는 가능한 집합에 있는 동물들 중에서 동물의 특성에 대해 질문을 합니다 (이 특성이 가능 집합을 더 좁히는 데 도움이 되지 않더라도). 엘시는 같은 특성에 대해 두 번 질문하지 않습니다.
베시와 엘시가 아는 모든 동물과 그들의 특성이 주어졌을 때, 엘시가 정확한 동물을 알게 되기 전에 받을 수 있는 "네" 대답의 최대 수를 구하세요.
입력
입력의 첫 번째 줄에는 동물의 수 N이 주어집니다 (2 ≤ N ≤ 100).
그 후, N개의 줄에 걸쳐 각 동물에 대한 정보가 주어집니다. 각 줄은 동물의 이름으로 시작하고, 그 다음에 정수 K가 주어지며, K는 해당 동물이 가진 특성의 수를 나타냅니다. 그 후 K개의 특성이 해당 동물에 대해 주어집니다. 동물의 이름과 특성은 최대 20개의 소문자 알파벳(a..z)로 이루어져 있습니다. 두 동물이 정확히 같은 특성을 가진 경우는 없습니다.
출력
게임이 끝나기 전에 엘시가 받을 수 있는 최대 "네" 대답의 수를 출력하세요.
예제
4
bird 2 flies eatsworms
cow 4 eatsgrass isawesome makesmilk goesmoo
sheep 1 eatsgrass
goat 2 makesmilk eatsgrass
3
이 예시에서는 엘시가 3개의 "네" 대답을 포함하는 전사를 생성할 수 있으며 (위의 예시처럼), 3개 이상의 "네" 대답을 포함하는 전사를 생성하는 것은 불가능합니다.
로그인해야 코드를 작성할 수 있어요.