시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17 4 4 28.571%

문제

이 문제에서 사전(dictionary)은 알파벳 오름차순으로 정렬된 여러 개의 단어를 가지고 있으며, 그 단어의 정의를 같은 언어로 표현한 것이다. 정의는 같은 사전 안에 있는 단어들로만 표현된다. 만약 사전이 N개의 단어를 정의한다면, 단어와 정의를 모두 포함해서 정확히 N개의 서로 다른 단어들만이 존재한다. 또한 우리가 알듯이, 단어를 정의하는 데 그 단어가 다시 등장하지는 않는다.

Sub-dictionary는 사전에 포함되는 단어만으로 구성될 수 있는 부분적인 사전이며, 역시 사전의 정의를 만족해야 한다. 즉, sub-dictionary 역시 등장하는 단어들은 모두 그 자신 안에 정의되어 있어야만 하는, 독립적으로 하나의 사전일 수 있는 개체이다.

컴퓨터에게 언어를 가르치기 위한 프로젝트가 활발히 진행 중이다. 먼저 우리는 컴퓨터에게 단어를 가르치기 위해 사전을 입력하기로 하였다. 그리고 그 사전의 단어들만으로 문장을 구성하여 컴퓨터에게 입력하면, 컴퓨터는 문장의 뜻을 해석하여 사용자가 원하는 행동을 할 수 있다.

그러나 컴퓨터가 단어를 혼자서 배우게 하는 것은 매우 어려웠다. 그래서 우리는 먼저 어떤 sub-dictionary의 모든 단어를 컴퓨터에게 수동으로 가르친 후, 그 단어들을 모두 이해하게 만들 것이다. 그 다음에는 주어진 단어들만으로 다른 사전의 모든 단어의 뜻을 이해할 수 있게 하고 싶다. 즉, 우리가 가르친 단어들만으로 정의된 또다른 단어가 있다면 컴퓨터는 그 단어 역시 배울 수 있으며, 그 단어 또한 다른 단어를 배우는 데 사용될 수 있다. 예를 들어 "xyz"라는 단어를 컴퓨터가 이해하려면, 단어 "xyz"의 정의에 사용된 다른 모든 단어를 컴퓨터가 알고 있어야 한다.

컴퓨터가 사전의 모든 단어를 스스로 학습할 수 있게 하는 최소 크기의 sub-dictionary를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 주어진다.

각 테스트 케이스의 첫 번째 줄에는 가르쳐야 할 사전에 있는 단어의 개수 n이 주어진다. (1 ≤ n ≤ 100)

그 다음 n개의 줄에 걸쳐 각 단어의 정의가 주어진다. 첫 번째 단어를 알기 위해서는 해당 줄의 나머지 단어들을 모두 알아야 함을 의미한다. 단어의 정의는 최대 30단어로 이루어져 있다.

각 단어는 공백으로 구분되며, 영소문자만으로 구성되어 있고 길이는 25글자 미만이다.

출력

각 테스트 케이스마다 첫째 줄에 최소 sub-dictionary에 속한 단어의 개수를, 둘째 줄에 속한 단어를 공백으로 구분하여 알파벳순으로 출력하시오.

예제 입력

5
aue oizer piqoi oizer
doy oizer hweqlo hweqlo
hweqlo piqoi aue
oizer piqoi
piqoi aue aue
0

예제 출력

3
aue oizer piqoi

힌트

출처

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2007 F번

  • 문제를 번역한 사람: kks227