Lining up argumentative children -------------------------------- There are n<=10 children. Fortunately, each child's first name starts with a different letter, so we can refer to the children by the initial letter of their name. Some pairs of children tend to get into fights. However, some children can keep the peace between certain argumentative pairs. For example, Aloysius and Egbert tend to fight. But if Egberts's big sister Brunhilde stands somewhere between Aloysius and Egbert, then Brunhilde will prevent Aloysius and Egbert from fighting with each other. We would like to line up all the children in single file in such a way that no fights will break out. For example, suppose we have 5 children, Aloysius, Brunhilde, Chuck, Dolores and Egbert and the following two constraints: * Brunhilde must be between Egbert and Aloysius * Dolores and Egbert must be between Chuck and Brunhilde Then, we can line up the children as follows: Aloysius Brunhilde Dolores Egbert Chuck Input ----- The input will consist of multiple instances. Each instance begins with two integers n > 0 and m >= 0 on a line. The next line contains a string of n distinct upper-case letters in alphabetical order. These are the first initials of the n children that must be lined up. Each of the next m lines contains a string of three upper-case characters XYZ indicating that the child with initial Y must be placed between the children with initials X and Z. The end of the input will be indicated by a line with n=m=0. (Do not produce any output for this line.) Output ------ For each input instance, output a string of n characters containing the initials of the children in an ordering that is consistent with all constraints. If there is more than one possible solution, output the first one in alphabetical order. Sample Input ------------ 5 3 ABCDE EBA CDB CEB 5 4 ABCDE EBA CDB CEB ECA 3 1 BFG BGF 0 0 Sample Output ------------- ABDEC No ordering possible BGF