MNIU - My Name is UMMM!
In a country far away there is a kind of a competition called programming contests. As they are becoming increasingly popular, they get regular coverage on newspapers. That's the only positive part of the story. The quality of their reports are not up to the mark and often hilarious for the competitive programming community. The reporters often mix up names - exchanging words from one person's name to someone else's name.
Chowdhury Shaheb - a curious programmer analyzed the reports and found a very interesting pattern. He saw whenever any word of two person's names have the same first and last letters and at least one additional common letter, journalists will mix them up. For example: The words 'Manjur' and 'Mazumder' have same first and last letters and two common letters 'a' and 'u'.
You'll be given a pair of names. List all possible confusing name variations of those two names. A confusing variation of a name is obtained by changing at least one word of that name to a similar word (according to the aforementioned pattern) from the other's name. A variation is not considered confusing if it is exactly same to any of the given names. See the input and output format section for more details.
Input
First line of input will contain a single integer T (1 <= T <= 15), the number of testcases. It will be followed by T sets of testcases. Each set of testcase will contain two lines, each line will contain a name. Each name will contain no more than 20 characters. Names will have no more than 3 words, each word will consist of only English letters ('A'- 'Z', 'a'-'z'). First letter of a word will always be capitalized and others are in lowercase. Each word of a name will be separated by exactly one space between them.
Output
First line of the output of each test case should contain the case number (In this format: Case <caseNumber>:). From the next line, print all the confusing variations - one per line in ascending lexicographic order. A name X is lexicographically smaller than another name B if it contains a smaller letter at the first position they differ or if X is a prefix of Y. A space is smaller than any other English character. If there is no confusing name, print "None" (without the quotes). Print a blank line between testcases.
Sample
Input 3 Syed Shahriar Manjur Pratyai Mazumder Tasnim Imran Sunny Sabbir Yousuf Sanny Md Hafiz Uddin Sohel Hafiz Output Case 1: Pratyai Manjur Syed Shahriar Mazumder Case 2: Sabbir Yousuf Sunny Tasnim Imran Sanny Case 3: None
Problem Setter: Mir Wasi Ahmed
Special Thanks: Ahmad Faiyaz
hide comments
nani:
2014-02-07 22:13:42
can please anyone tell me if input is:
|
|
Hector Monteo:
2014-01-31 13:18:08
Can someone give me a test case? |
|
[Lakshman]:
2014-01-09 15:36:50
@Ahmad Faiyaz Can you Please reply? |
|
Jacob Plachta:
2014-01-02 08:29:05
Hmm, is the data definitely correct? I'm pretty sure I've read the problem correctly.
|
Added by: | Faiyaz |
Date: | 2013-12-30 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |