Marriage Success (MS) is a marriage counseling service advising couples on how to improve the ‘get along’ experience. MS’s idea is simple: each spouse writes down his/her preferences for various criteria of common interest. “Our criteria go beyond physical appearance and passion that guide early romance and tend to blind judgement. We want to understand your values as you live day by day. Happy couples are those whose preferences are compatible or can be made compatible.” Suppose X and Y are qualities to be considered. If a person declares that X > Y , it means that this person prefers quality X to quality Y (it does not mean that his/her mate should have a quality, it is only an opinion). Preferences are obviously irreflexive (i.e., X ̸> X) and they are transitive (i.e., ifX>Y andY >Z,thenX>Z–whichcanbeabbreviatedasX>Y >Z). A couple is fully compatible if the preferences of the spouses are consistent, that is, if it is possible to arrange the qualities of interest of the spouses in a compatibility list reflecting both of their preferences. In this case, if a spouse says X > Y , qualities X and Y must occur in the compatibility list and moreover X must be preferred over Y . If a couple is not fully compatible, then perhaps at least it is passably compatible: their preferences can be made consistent if some spouse drops at most one preference. For example, newly-wed Alice and Bob declare their preferences with respect to the following qual- ities (that they observe in a possible mate): biker, cultured, enthusiastic, foodie, juggler, kayaker, movies, organized, puzzles, rich, theatre, and windsurfer. Their preferences are (observe that they could say nothing about qualities meaning that such quality does not have any importance): Alice: organized > puzzles > rich, windsurfer > theatre, and rich > movies. Bob: kayaker > movies > puzzles and rich > theatre. In this case Alice and Bob are not fully compatible. To see that, a compatibility list should have rich before movies (Alice), movies before puzzles (Bob), and puzzles before rich (Alice), meaning that rich must occur before rich which is impossible. However, the couple is passably compatible: if Alice drops her preference rich > movies, then there is a compatibility list modeling both of their preferences: kayaker > organized > movies > puzzles > rich > windsurfer > theatre. MS needs a software solution to determine if clients are full compatible, passably compatible or none of these. Can you help? Input The problem input consists of several test cases, each one defined by a set of lines establishing preferences of a couple. A test case is defined as follows: • the first line contains two strings A and B, separated by blanks, representing the name of the spouses, • the second line is a sequence of strings of the form (one or more blanks separating items, including commas and final semicolon): q11 q12 ... q1r1 , q21 q22 ... q2r2 , ... , qm1 qm2 ... qmrm; meaning that person A has sets of preferences (qij’s are strings denoting qualities): q11 > q12 > ... > q1r1,q21 > q22... > q2r2,...,qm1 > qm2 > ... > qmrm
2/2 • the third line is of the form above representing the preferences of B. Please consider that a quality name is a string with more than 0 and less than 11 characters, that couples may declare opinions about at most 100 different qualities, and that is guaranteed that the given data is well defined with respect to the above rules. Also, it is guaranteed that the information corresponding to each person does not include preference cycles (i.e., each person is self-compatible). The end of the input is recognized by a line with A = B = ∗. Output For each given case, output one line with a single character F, P, or N, meaning that couple with spouses A and B is full compatible, passably compatible, or not compatible, respectively. Sample Input Alice1 Bob1 organized puzzles rich , windsurfer theatre , rich movies ; kayaker movies puzzles , rich theatre ; Alice2 Bob2 organized puzzles rich , windsurfer theatre ; kayaker movies puzzles , rich theatre ; Alice3 Bob3 young busy rich , wallet tennis , rich movies , busy toys ; toys movies busy , rich tennis busy , rich movies ; ** Sample Output P F N