Following Orders (experts only)

Time Limit: 9000 ms Memory Limit: 10000 KiB

Problem Description

Background
 
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.
 
The Problem
 
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.
 

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  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.

Output

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.

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

Hint


Source