Problem 1009: Toga Party

(ACM S.E. U.S.A. Regional 2003, problem 9)

Description

The guys at Delta House are at it again. They.ve decided to throw the ultimate toga party. Since they want this to be the best party Faber College has ever seen, they've decided to match up the men and women attending the party in such a way as to maximize the .happiness quotient.. The happiness quotient contributed by a pairing is determined by the following sequence of rules:
  1. If a pairing has a man and a woman who like each other, a happiness quotient of 4 is contributed to the party.
  2. Otherwise, if a pairing has a man and a woman who at least tolerate each other, a happiness quotient contributed is 3.
  3. Otherwise, if the woman in a pairing at least tolerates the man, the happiness quotient contributed is 2.
  4. Otherwise, if the man in a pairing at least tolerates the woman, the happiness quotient contributed is 1.
  5. In all other cases, no happiness quotient is contributed.
So, if Fred, Bob, and Greg were at the party with Janet, Mary, Cindy, and Dianne, and the following preference facts were known:
  • Fred likes Janet
  • Fred likes Mary
  • Fred tolerates Cindy
  • Bob tolerates Janet
  • Greg tolerates Mary

     
  • Janet likes Fred
  • Mary tolerates Fred
  • Janet tolerates Bob
  • Mary likes Bob
  • Mary tolerates Greg
  • Cindy tolerates Fred
  • Cindy likes Bob
the highest happiness quotient that the party could have would be 9, obtained by matching Fred and Janet (4 points) and Greg and Mary (3 points), and Bob and Cindy (2 points).

Given a number of preference facts, you should determine the maximum happiness quotient that is possible for a party. Each person can be matched with at most one other person at the party. There may be a different number of men and women.

Input Format

The first line of each data set contains a non-negative integer n, which is the number of rules for that party. There will then be n lines, each with three letters on the line, c1Fc2. Within a rule, the men are identified by lowercase letters ('a'-'z') and the women are identified by uppercase letters ('A'-'Z'). Character c1 and c2 will identify a man and woman (in either order). The F is either an 'L' or 'T', with 'L' indicating c1 likes c2, and 'T' indicating c1 tolerates c2. (For example, aLB represents "a likes B" and GTg represents "G tolerates g".) Each combination c1 and c2 will appear at most one time in the input, so you do not need to be concerned with conflicting input (e.g., you will not have both aLB and aTB in the same set, but you may have aLB and BTa, since in the first c1 = a and in the second c1 = B). There will always fewer than 9 men, and fewer than 9 women.

The last data set is flagged by the number of rules being zero. This set should not be processed.

Output Format

Each data set should generate a single line of output in the form
Party n has a maximum happiness quotient of h
where n is the number of the data set (starting at 1), and h is the maximum happiness quotient.

Sample Input

12
fLJ
fLM
fTC
bTJ
gTM
JLf
MTf
JTb
MLb
MTg
CTf
CLb
4
ATa
ATb
aTA
bTA
6
ALa
CLa
CLb
aTA
aLC
bTC
0

Sample Output

Party 1 has a maximum happiness quotient of 9
Party 2 has a maximum happiness quotient of 3
Party 3 has a maximum happiness quotient of 6

End of Problem