CareerCup

Write a pseudo code. The question aims to test both your programming and analytical skills. Your implementation will be tested for both time and space efficiency.

The input format is strictly followed. Your program will be evaluated for correctness against multiple inputs. Some inputs will be very large (> 100,000 nodes).


Problem Statement

You are in-charge of the office jukebox. You are determined to do a very good job and make your colleagues happy. You ask them to email you a list of music bands they like. The number of bands each colleague likes is limited to 10,000.

Input

All input will be given on stdin. Your input will be of the form,

1. The first line will be an integer stating the number of lines of input.
2. The input will only contain alphanumeric characters, colon, comma, underscore and space [A-Z, a-z, 0-9, _, , ], +.
3. The first word will be the name of your colleague, followed by a colon.
4. A comma separated list of that person’s favourite bands will follow the colon.
5. Every line will be terminated by a newline character (\n).

An example input would look like:

6
Anne: Metallica, The_Doors, Black_Sabbath
John: The_Beatles, The_Doors, Metallica, Pink_Floyd
Kathy: U2, Guns_n_Roses, Led_Zeppelin
Jamie: Radiohead
Ashok: Guns_n_Roses, U2, Pink_Floyd, The_Doors
Sara: Blink_182, Iron_Maiden, The_Doors


Problem

You decide to use your data to find the people most compatible with each other. Two people are compatible if they have at least 2 bands in common. The compatibility of two people is directly proportional to the number of bands they like in common.

For each person in the list, output the most compatible person(s). If there is more than one compatible person, separate the names with a comma. If a person has nobody compatible, output nothing. For our example input, the output will be,

Anne: John
John: Anne, Ashok
Kathy: Ashok
Jamie:
Ashok: John, Kathy
Sara: