New update is available. Click here to update.

Synonymous Sentences

Posted: 16 Mar, 2021
Difficulty: Moderate


Try Problem

You are given a sentence consisting of several space-separated words and a list of pairs of synonyms. Your task is to find out all possible sentences that can be formed by replacing any word in the sentence with any of its synonyms.

Note :

1. A word may or may not have synonyms.
2. There can be multiple synonyms for a single word.
3. All words only contain lowercase English letters.
Input Format :
The first line contains an integer T, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains two space-separated integers, N and M, denoting the number of pairs of synonyms in the list and the number of words in the sentence.

The second line contains 2*N space-separated words. For every, i from 1 to N, (2*i-1)-th and (2*i)-th words are synonyms of each other.

The third line contains M space-separated words which form the sentence.
Output Format :
For each test case, print in separate lines all sentences that can be formed by replacing one or more words with their synonyms. 

Please note that all the sentences must be printed in lexicographically sorted order.

The output of every test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N,M <= 8
1 <= |word| <= 10

Where |word| denotes the length of any word that appears in the sentence.

Time Limit: 1sec