solve in python

You and your friend want to name the new dog on the street. You will pick the firstname and he will pick the lastname. However, turns out that both of you have faulty vocabularies. You only know certain english alphabets, and he knows certain other. Print all possible names that you and your friend can come up with given that you both use all the letters you know, exactly once, to form a name and you pick the first name and he picks the lastname. Use recursion for printing all the names. You must print all the names in lexicographically increasing order. Input Format The first line contains a string of the alphabets known by you, all distinct. The second line contains a string of the alphabets known by him, all distinct. *The first and the last name may contain common letters. The letters are only distinct within the names themselves. Output all the names in separate lines with a space in between the name and the surname. See the sample for a better understanding of the