| Following Orders |
Order is an important concept in mathematics and in computer science. For example, Zorn's Lemma states: ``a partially ordered set in which every chain has an upper bound contains a maximal element.'' Order is also important in reasoning about the fix-point semantics of programs.
This problem involves neither Zorn's Lemma nor fix-point semantics, but does involve order.
Given a list of variable constraints of the form
x < y, you are to write a program that prints all
orderings of the variables that are consistent with the constraints.
For example, given the constraints x < y and x < z there
are two orderings of the variables x, y, and z that are consistent with these
constraints: x y z and x z y.
The input consists of a sequence of constraint specifications. A
specification consists of two lines: a list of variables on one line
followed by a list of contraints on the next line. A constraint is
given by a pair of variables,
where x y indicates that x < y.
All variables are single character, lower-case letters. There will be at least two variables, and no more than 20 variables in a specification. There will be at least one constraint, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the contraints in a specification.
Input is terminated by end-of-file.
For each constraint specification, all orderings consistent with the constraints should be printed. Orderings are printed in lexicographical (alphabetical) order, one per line. Characters on a line are separated by whitespace.
Output for different constraint specifications is separated by a blank line.
a b f g a b b f v w x y z v y x v z v w v
abfg abgf agbf gabf wxzvy wzxvy xwzvy xzwvy zwxvy zxwvy