Following Orders
Description
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 constraints.
For example, given the constraints x<y and x<z there is two orderings of the variables x, y, and z that are consistent with these constraints: x y z and x z y.
Input
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 constraints on the next line. A constraints 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, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the constraints in a specification.
Input is terminated by end-of-file
Output
For each constraint specification, all orderings consistent with the constraints should be printed.
Orderings are printed in lexicographical (alphabetical) order, one per line.
Sample input
a b f g
a b b f
v w x y z
v y x v z v w v
sample output
abfg
abgf
agbf
gabf
wxzvy
wzxvy
xwzvy
xzwvy
zwxvy
zxwvy
參考答案:dos