给出n个互不相同的小写字母，表示出现的字符类型，以及k个约束关系：<a1 b1> <a2 b2> <a3 b3>.....<ak bk>，表示ai必须出现在bi前面(ai,bi不会超出所给字符类型的范围，且ai!=bi)。

请按照字典序输出所有满足约束条件的序列

如:

n=3，字符类型为：x y z

k=1，约束条件为：x z，表示x必须出现在z的前面。

所有满足约束条件的排列有：

xyz

xzy

yxz

第1行，2个整数n和k（1 < n < 9，1 ≤ k ≤ 8）

第2行，n个空格隔开的字符

接下来k行，每行二个字符ai和bi（表示约束关系），数据保证不会出现矛盾的关系。