|
D |
Airbus
vs. Boeing Input: Standard Input Output: Standard Output |
|
Airbus & Boeing are the two giant names in the aircraft manufacturing industry of today. Both of these reputed companies have a number of distinguished aircrafts. Due to the competitive nature of the market, comparisons have been made between different aircraft models and very often a certain aircraft from Airbus has been termed similar to some Boeing aircraft model. For example, Boeing 737 has historically been linked with Airbus A320 as the same category aircraft. To make things more complicated, the relationships are not always one to one. The recent Boeing 787-9 DreamLiners are very well compared with both Airbus A340-500 as well as Airbus A350-800. There are many other such cases.
In your first day of work at 'So Many Problems' Airport, the airport manager hands you over a list containing a number of aircraft pairs. At first observation you realize that the list can essentially be modeled as a graph where an edge between two aircraft models means that these two aircrafts are manufactured by different companies but are similar to each other. You have also noticed that, the graph never has a cycle. On the other hand, you have found that the list has a major flaw. In this list, the aircrafts are mentioned only using the model numbers but the manufacturer names are omitted. So, the fact that Boeing 747-8 is similar to Airbus A380, is stated as "747-8 A380" in the list.
What you are trying to do is to divide all the aircrafts from the input list into two sublists - one per each manufacturer. Moreover, each of the lists will have to be in sorted order i.e. if there are two aircrafts in a sublist, the better aircraft between them should be ranked higher in the sublist. Now, you are not given any input about which aircraft is better than whichever other aircraft. Also, you have no idea about which models are Airbus models while which are Boeing models. Naturally, you can create the two sorted sublists in many possible way and still you won't know which one is the right one. By this time, you have begun to doubt that some of the given similarity reports might not be valid at all. For example, if your final sorted sublists are [A, B] & [C, D] & your input list shows that A is similar to D & B is similar to C - clearly one of these two similarities are wrong.
The first thing you are trying to find is, given the input similarities, at most how many of them might be valid for any configuration of the two input sublists.
Input
There will be at most 60 test cases in the input file. Each case begins with an integer N (1<=N<=100), the number of different aircraft models in the list. Each of the next N lines contain a unique string, the name of an aircraft model. This string will be upto 10 characters and will contain upper case letter and digits only. Then follows an integer E (E>=0), the number of similarities in the list. Each similarity is described in a line by a pair of aircraft model names separated by a space. Each line denotes that the pair of aircrafts in that line are created by two separate manufacturers and are similar to each other. There will be no invalid model names.
The end of input will be denoted by a case with N = 0. This case should not be processed.
Output
For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the maximum possible number of valid similarities in the input list.
Sample
Input Output
for Sample Input
|
7 A380 777 A340 747 787 757 767 6 A380 747 A380 787 A380 777 777 A340 757 A340 767 A340 7 777 A380 A340 A320 737 747 757 6 777 A380 A380 747 777 A340 A340 757 777 A320 A320 737 0 |
Case 1: 6 Case 2: 5 |
Problemsetter: Mohammad Mahmudur Rahman, Special
Thanks: Manzurur Rahman Khan
Explanation
of sample input:
In the first sample, the 7 aircraft models can be divided into two sorted lists with keeping all the 6 similarities consistent. For example, suppose one of the list is [A380, A340] (in given order) and the other list is [747, 787, 777, 757, 767] (in given order). Now, if we draw lines from aircrafts of left list to it's similar aircrafts from right list, there will be no crossing.
But in the second sample, no matter how we divide and sort the input list, there will be at least one inconsistent similarity. Let's assume our sorted lists are [747, 777, 757, 737] and [A380, A340, A320]. Then we can see that, in the left list, 777 is a higher rank aircraft than 757 while A340 is a higher rank aircraft than A320. But in our input list, 777 is linked with A320 while 757 with A340. Clearly, one of these two similarities must be invalid. If you check other possible combinations for the two lists, you will find that there are one or more invalid similarities. So, the maximum number of valid similarities is 6 - 1 = 5.