Description

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.

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.

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

Source

题目描述

在数学和计算机科学中，“序” 是一个重要的概念。例如，佐恩引理指出：“每个链都有上界的偏序集包含一个极大元。” 序在程序不动点语义的推理中也很重要。

本题既不涉及佐恩引理，也不涉及不动点语义，但确实与序相关。给定一组形如 x < y 的变量约束条件，你需要编写一个程序，输出所有与约束条件一致的变量排列顺序。

例如，给定约束条件 x < y 和 ​x < z​，变量 x、y、z 的合法排列有两种：x y z 和 ​x z y​。

输入格式

输入由一系列约束规范组成。每个规范包含两行：第一行是变量列表，第二行是约束条件列表。每个约束条件由一对变量表示，如 x y 表示 ​x < y​。

所有变量均为单个小写字母。每个规范中至少包含 2 个变量，最多 20 个变量；至少包含 1 条约束条件，最多 50 条约束条件。每个规范至少存在 1 种合法排列，最多 300 种合法排列。

输入以文件结束符（EOF）终止。

输出格式

对每个约束规范，按字典序（字母顺序）输出所有合法的变量排列，每行一个。不同规范的输出之间用一个空行分隔。

输入输出样例 #1

输入 #1

a b f g
a b b f
v w x y z
v y x v z v w v

输出 #1

abfg
abgf
agbf
gabf

wxzvy
wzxvy
xwzvy
xzwvy
zwxvy
zxwvy