Alien Alphabet Order (acm16n_alpha)

Time limit:
1000 ms
Memory limit:
128 MB

You are a language scientist or a linguist at NASA. Currently, you are in a secret mission because NASA just made the first contact with an alien race. Well, as you have seen from many movies, there is a higher chance to have a big war with them. So, your job is to avoid the war by telling them “don’t fight, let’s be friend”. However, we do not know their language. What NASA has is a sequence of signals which is represented by a sequence of English characters for simplicity.

Your job is to find the ordering of characters (i.e., the collating sequence) in alien language. In particular, your program will take a set of strings that has been sorted according to a particular collating sequence and determine what that sequence is.


The input consists of a multiple set of t test cases, 1 ≤ t ≤ 10. The first line will be an integer t indicating the number of test cases. Each test case consists of an ordered list of strings of uppercase letters, one string per line. Each string contains at most 100 characters. The end of the list is determined by a line that contains a single character ‘#’. The list size is at most 100 strings. The list will imply a complete ordering among those letters that are used. A sample input file is shown.


For each test case, your output should be a single line containing uppercase letters in the order that specifies the collating sequence used in producing the input data file. Correct output for the data file above is shown below.



Select description language

English (raw)

If you don't find what you want

Translate it!

Edit this description