이중 언어

Elliot의 부모는 집에서 Elliot에게 프랑스어와 영어로 말한다. Elliot은 많은 단어를 들었지만, 어떤 단어가 어느 언어에서 온 것인지는 항상 분명하지 않다! Elliot은 영어라고 확신하는 문장 하나와 프랑스어라고 확신하는 문장 하나를 알고 있으며, 영어일 수도 프랑스어일 수도 있는 다른 문장들도 알고 있다. 어떤 단어가 영어 문장에 등장한다면, 그 단어는 반드시 영어 단어여야 한다. 어떤 단어가 프랑스어 문장에 등장한다면, 그 단어는 반드시 프랑스어 단어여야 한다.

Elliot이 들은 모든 문장을 고려할 때, Elliot이 들은 단어 중 반드시 영어와 프랑스어 양쪽 모두의 단어여야 하는 단어 수로 가능한 최솟값은 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 25. 각 단어는 최대 10개의 문자로 이루어진다. 두 "known" 문장은 각각 최대 1000개의 단어를 포함한다. "unknown" 문장은 각각 최대 10개의 단어를 포함한다.

작은 데이터셋

시간 제한: 240초. 2 ≤ N ≤ 20.

큰 데이터셋

시간 제한: 480초. 2 ≤ N ≤ 200.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N이 포함된 한 줄로 시작한다. 이어지는 N개의 줄에는 각각 공백으로 구분된 일련의 "words"이 주어진다. 각 "word"은 소문자 a-z만으로 이루어진다. 이 N개 줄 중 첫 번째 줄은 영어로 된 "sentence"이고, 두 번째 줄은 프랑스어로 된 "sentence"이다. 나머지는 영어 또는 프랑스어로 된 "sentences"일 수 있다. ("words"과 "sentences"이 실제 언어에서 유효하다고 보장되지는 않는다는 점에 유의하라.)

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 Elliot이 들은 단어 중 반드시 영어와 프랑스어 양쪽 모두의 단어여야 하는 단어 수의 최솟값이다.

Case #1에서 Elliot은 첫 번째 문장이 영어이고 두 번째 문장이 프랑스어라는 것을 확실히 알고 있으므로 모호함이 없다. 영어와 프랑스어 양쪽 모두에 반드시 속해야 하는 유일한 단어는 "baguettes"이다.

Case #2에서 마지막 두 문장은 English English, English French, French English, 또는 French French 중 하나일 수 있다. 이 가능성들 중 두 번째 것이 두 언어에 공통인 단어 수를 최소화하며, 그 집합은 d, e, i, j인 것으로 밝혀진다.