BlindFold

A labyrinth is a set of interconnected rooms. Each room has a few doors, each door is labelled, just on one side, by either “A”, “B”, “C” or “D”. There might be more than one door in a room with the same label, and each door in a room always leads to a room (sometimes the same room!) in the labyrinth, through a dark and convoluted tunnel. Moreover, doors may only be opened from their labelled side, so after getting through a door to another room, you may only use the new labelled doors you may find there. Given two labyrinths L1 and L2, and a room R1 of L1 and R2 of L2, we say that R1 is equivalent to R2 if the two following conditions hold:

1. For each door labelled with x in R1 one may choose a door labelled with the same label x in R2 such that the two doors lead to equivalent rooms R1’ and R2’ (of L1 and L2 respectively).
2. For each door labelled with x in R2 one may choose a door labelled with the same label x in R1 such that the two doors lead to equivalent rooms R2’ and R1’ (of L2 and L1 respectively). Notice that if R1 and R2 are equivalent rooms then the set of door labels in R1 is the same as the set of door labels of R2. We say that the labyrinths L1 and L2 are equivalent if their initial rooms are equivalent. We are asked to write a program that checks whether two labyrinths are equivalent according to the definition above. Input The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line. The input specifies the structure of the two labyrinths, one after the other. The specification of each labyrinth is as follows. First, an integer N indicates the total number of doors in the labyrinth. Then, for each each door, a line of the form i a d follows, where i is an integer indicating the initial room, a is the door label (one of ‘A’, ‘B’, ‘C’, ‘D’) and d is an integer indicating the destination room. Different doors in a room may well be labelled with the same letter. By convention, the visitor starts the visit in room 1. The labyrinths considered will not have more than 200 rooms. Rooms are numbered 1, 2, . . . , etc. Output For each test case, the output must follow the description below. A single line containing ‘yes’ if the two labyrinths are equivalent, and ‘no’ if they are not equivalent. Sample Input 2 1A2 2A1 3 1A1 1A2 2A2

2/2 4 1A2 2B1 2A3 3C1 5 1A2 1A4 2A3 3C1 4B1 Sample Output yes no