HZNUOJ

Archer和Lancer的字符串游戏

Tags:   暴力回溯法
Time Limit:  2 s      Memory Limit:   128 MB
Submission:136     AC:39     Score:97.64

Description

Lancer和Archer聚在一起玩游戏了,这一次的游戏很简单,就是Lancer和Archer各自拿着一个字符串,然后在不改变自己的字符串顺序的情况下请输出所有可能的字符串组合?
例如:
Lancer选ab,Archer选cd,那么只有abcd,acbd,acdb,cdab,cadb,cabd这几种。bacd就不行,因为Lancer原字符串中a在b前面,那么在组合的过程中a也一定要在b前面。abdc不行,也是同样的道理。

Input

首先输入一个整数t,代表接下来有多少组字符串(t<=100)
接下来t行,每行输入一组两个字符串,两个字符串长度均小于等于8且长度都至少为1,且都是由26个小写字母组成

Output

所有可能的字符串组合,按字母序从小到大输出,每组字符串后面输出一个空行.。输出的过程中相等的字符串只输出一次。

Samples

input
2 v d ab cd
output
dv vd abcd acbd acdb cabd cadb cdab

Author

YE, Lei