TRIP  Trip
Alice and Bob want to go on holiday. Each of them has drawn up a list of cities to be visited in turn. A list may contain a city more than once. As they want to travel together, they have to agree upon a common route. No one wants to change the order of the cities on his list or add other cities. Therefore they have no choice but to remove some cities from the list. Of course the common route is to involve as much sightseeing in cities as possible. There are exactly 26 cities in the region. Therefore they are encoded on the lists as lower case letters from 'a' to 'z'.
Input
The first line of input contains a number T <= 10 that indicates the number of test cases to follow. Each test case consists of two lines; the first line is the list of Alice, the second line is the list of Bob. Each list consists of 1 to 80 lower case letters.
Output
The output for each test case should contain all different trips exactly once that meet the conditions described above. There is at least one such trip, but never more than 1000 different ones. You should order the trips in lexicographic order. Print one blank line between the output of different test cases.
Example
Input
1 abcabcaa acbacba
Output
ababa abaca abcba acaba acaca acbaa acbca
hide comments
shamimice03:
20200516 13:51:09
Using the BottomUp table you can store all the LCS. For storing LCS use SET. 

jlpb97:
20190716 02:04:20
we can avoid bactracking, the bottomup table stores a set of all the LCSs. 

inderjeet_777:
20180924 08:45:39
lcs + backtracking gives Tle...wasted much time on that


tanishkbansal:
20180615 15:38:06
i am not getting what we have to give in output 

Simes:
20180524 18:14:18
Hey @imkiller, why do you keep posting links to your code after you solve a problem? Not good imho.


horizon121:
20180509 15:32:52
Problem is simple just be clever during backtracking using recursion


ahaunul_kader:
20180129 07:37:24
why the don't start their journey from b/c???i mean why always from 1st index???


ashishranjan28:
20161104 06:05:31
backtracking + lcs 

Nallagatla Manikanta:
20160810 16:03:59
hell of code :( 

SUBHAJIT GORAI:
20160524 21:16:53
MY solution passed using sets and vector , just use it in a proper way .HINT (in the question it is mentioned : " but never more than 1000 DIFFERENT ones "). 
Added by:  Adrian Kuegel 
Date:  20040605 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  own problem, used in CEOI 2003 