Woburn Challenge 1998

INPUT FILE: prob4.in
OUTPUT FILE: prob4.out

Dr. Evil, having escaped from Austin Powers last time, is trying a new strategy to extort money from mankind. He has decided to clone himself so that he can make his own fleet of Dr. Evil stormtroopers. Then, and only then, can he successfully hold the United Nations for ransom for the princely sum of � 1 million dollars. He hires the best Evil scientists to extract his DNA and then determine its sequence so that they can make clones of him. However, sequencing technology is not very efficient and yields several fragments of Dr. Evil's DNA. If you put all the fragments together, you will get his entire DNA. However, as a consequence of DNA sequencing, the ends of a fragment are sometimes duplicated at the beginning of next fragment. His scientists are now trying to put these fragments together to form the shortest possible sequence. This, they figure, will be Dr. Evil's DNA. (Little did they know that this very same technique resulted in tragic consequences when Mr. Bigglesworth was "cloned" from Chewbacca's DNA). Note that Dr. Evil is not a bacterium and so his DNA is linear (not circular).

INPUT
A series of at most 10 strings (each with at most 10 characters) representing DNA fragments (one fragment per line). Note that the strings are in some random order and not necessarily in the order in which they appear in the completed DNA. This will be followed by a 0 (zero) to indicate that the input set is over. This will then be followed by more fragments representing a new DNA strand followed by another 0 and so on till the end of the file.

OUTPUT
Put the strings together in some order to produce the smallest DNA strand. Output that DNA strand (one per line for each set). In the event that this strand is not unique, you may output any shortest DNA strand.

Sample Input File

AC
CCC
CGT
TAC
0
ACCT
CGA
CCTACG
0

Output for Sample Input

TACCCGT
ACCTACGA

Note: the 1st output is not unique

How: (this is just for your own reference - you do not need to output how the fragments fit together)

TAC
 AC
  CCC
    CGT


ACCT
 CCTACG
     CGA