Welcome to ZOJ
96 - ZOJ Monthly, September 2010 - B
Change the Major

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The students in Zhejiang University major in three subjects: Computer Science, Mathematics, and Chinese. But some of them don't like their majoring subjects. They want to change their majors. According to the rules of the Zhejiang University, if a student wants change his major from major A to major B, his GPA must be the highest one of all the students' in major A and higher than every students' in major B(or there is no student in major B).

Recently, there is something wrong between College of Computer Science and Department of Mathematics, the students couldn't change their majors directly between Computer Science and Mathematics. If a student wants to change from Computer Science to Mathematics, he needs to change to Chinese first.

Everyone is willing to change his major temporarily, if it can help others study in their favorite majors. The office can only deal with one application in one day. How many days it needs to take at least to satisfy all students (move all students to their favorite majors)?


The first line containing an integer n (1 <= n <= 19) indicates the number of the students. For the following n lines, each line has the format: "Original Major","Favorite Major",G. G is a float number representing the GPA of the student (0 <= G <= 5). It has exactly two digits after the decimal point. Any two students' GPA are different.

"Original Major","Favorite Major" can only be "Computer,Chinese,Mathematics".


One integer, the minimum days it needs to takes.

Sample Input

Computer Chinese 3.50
Chinese Chinese 4.40
Mathematics Computer 3.00

Sample Output



the first case:
Day 1: The second student changes his major from Chinese to Mathematics.
Day 2: The first student changes his major from Computer Science to Chinese.
Day 3: The second student changes his major from Mathematics to Chinese.

Author: LIANG, Jiaxing
Contest: ZOJ Monthly, September 2010
Submit    Status