2367. Sub-dictionary

单点时限: 2.0 sec

内存限制: 256 MB

In this problem, by the word “dictionary” we mean a list of alphabetically ordered words and their associated explanations in the same language. A dictionary must contain the definition for any word that appears in the explanation of another word. So you see, if a dictionary defines $N$ words, it has exactly $N$ distinct words in it. Also, we know that in a dictionary no word appears in the definition of itself.

A sub-dictionary is a collection of dictionary’s words and their definitions such that it can be published as an independent dictionary, obviously satisfying the mentioned condition. As a project of Computational Linguistics course, we are assigned to create a Lexical Knowledge Base which is the knowledge expressed by words. For this task we should create our knowledge foundation based on a dictionary.

It’s really hard for the computer to study words automatically. So, we decided to manually teach it some common words. We start from an appropriate sub-dictionary. By understanding its words, a computer could extend its knowledge to the whole dictionary word by word. For instance, a word “xyz” could be added to the computer’s understanding if computer knows the meaning of every words used in xyz’s definition. You are asked to write a program that can find the smallest extendable sub-dictionary for a specific dictionary.


The input consists of multiple test cases. The first line of each test case is $n$ ($1 \le n \le 100$), the number of dictionary’s words. Each of the next $n$ lines contains a word and its definition (that has at most $30$ words). Words are separated by blanks and are made up of small English letters less than $25$ characters.


For each test case, on the first line print the number of sub-dictionary’s words and on the second line write the alphabetically sorted list of words (separated by blanks).


aue oizer piqoi oizer
doy oizer hweqlo hweqlo
hweqlo piqoi aue
oizer piqoi
piqoi aue aue
aue oizer piqoi

3 人解决,13 人已尝试。

3 份提交通过,共有 45 份提交。

9.3 EMB 奖励。

创建: 11 年,10 月前.

修改: 2 年,7 月前.

最后提交: 2 年,3 月前.

来源: Tehran 2007-2008