Problem C
Flag Quiz
However, sometimes (actually, most of the time) you can figure out the answer to a quiz question just by looking at the alternatives. Being a low budget show, the underpaid quiz question authors strive to minimize their effort in coming up with the alternatives for each question. They construct each alternative by making a small number of changes to the correct answer, where a change consists of replacing one part of the correct answer with something else. For example, transforming “green, blue, stripes” into “green, yellow, stripes” has one single change, while changing the same answer into “life, universe, stripes” has two changes. The question authors never permute the parts, so order matters. In other words, transforming “green, blue, stripes” into “stripes, blue, green” has two changes even though they are both technically the same answer. Note that the answers are case sensitive, so “green, blue, stripes” and “Green, Blue, Stripes” need 3 changes.
Your task is to write a program that automatically finds the most likely answers to questions constructed in this way. Define the incongruousity of an alternative as the maximum number of changes needed to transform that alternative into any of the other alternatives. We then seek the alternative(s) with the smallest incongruousity.
Task
Given a question and a set of potential answers to it, find the answer that is easiest to change into any other answer.
Input
The first line is the question to be answered. The next line contains one positive integer $1 \leq N \leq 100$, giving the number of answer alternatives. The next $N$ lines contain one alternative each. The alternatives are lists of parts, separated by a comma and a space. All answers have the same number of parts, at most 100. All parts are strings of letters a-z and A-Z, digits 0-9 and spaces. Each part doesn’t contain leading or trailing spaces (except the space after a comma that separates 2 parts). The maximal length of a part is 50 characters.
Output
Output the alternative that requires the smallest maximum amount of changes to be turned into any other answer. If there are several least incongruous alternatives, output them all in the same order as in the input.
| Sample Input 1 | Sample Output 1 |
|---|---|
The flag of the empire Angola? 4 Green stripe, black stripe, yellow Red stripe, black stripe, yellow Red stripe, black stripe, white Red stripe, green stripe, yellow |
Red stripe, black stripe, yellow |
| Sample Input 2 | Sample Output 2 |
|---|---|
The flag of the Knights who say Ni? 4 Black, white, pink, shrubbery Black, white, red, shrubbery Pink, white, red, shrubbery Black, pink, red, shrubbery |
Black, white, red, shrubbery |
