The Writers' Club#1632

The Writers' Club

1 second

64 megabytes

Easy

Forget Facebook, forget Second Life, The Writers' Club is the next big thing on the Internet. The Writers' Club is a platform where both writers and lovers of short stories can meet, publish, read, and discuss writers' promising contributions. Like any other Internet virtual community, the website allows readers to create lists of their favorite writers. The website administrators have noticed that readers tend to favor writers already favored by their favorite writers. For example, if John likes the stories written by Alice, then many readers who like John's stories also like Alice's. Moreover, John's readers tend to admire Alice's favorite writers as well.

The website would like to start a recommendation service based on this observation. Continuing with the example above, the website would like to recommend Alice (and her favorite writers, and their favorite writers, and so on) to all of John's readers. Naturally, the recommendation service has to be smart enough not to recommend a writer who is already favored by the reader receiving the recommendation.

Input

Your program will be tested on one or more test cases. The first line of a test case specifies two positive integers: $T$ and $N$ , where $T$ is the total number of users (not exceeding $100000$ ) and $N$ is the number of writers (not exceeding $100$ ). $N$ lines follow, one for each writer. Each line consists of one or more names, the first being the name of a writer and the remaining being the names of admirers of that writer. For example:

writer reader_1 reader_2 … reader_d

Here, writer is the writer's name, and reader_1 … reader_d are the names of the writer's admirers. A name is a sequence of one or more lowercase letters, no longer than $16$ characters. Names are unique throughout the test case. Names are separated by one or more spaces.

The last line of the input file consists of two zeros.

Output

For each test case, the first line of the output should be:

— CASE k

Where $k$ is the test case number (starting at $1$ ), and '-' is the minus sign.

Following that, there should be zero or more lines, one for each writer being recommended. The format is:

writer reader_1 reader_2 ...

Where writer is the name of the writer to be recommended for reader_1, reader_2, and so on. The output lines should be sorted alphabetically by writers, and for each writer, readers should also be sorted alphabetically. No writer should be recommended for himself. All names in the output are separated by a single space.

Examples

Example 1