Hi everyone! I can't solve this problem, can you help me please?
Given a list of words, you have to find an order in which a word A can be before to word B only if the last letter of A is the same that the first letter of B. This order must be circular, like this:
(LEFT: Given words. RIGHT: A possible ordering of the words)
Input: First line, the quantity of words N (1 <= N <= 9000). Next N lines have the words (one word per line). Lenght of each word don't exceed 6:
6 arbol orden susana otro listo nexos
Output: If it's possible to make the circular ordering, print N lines with the words ordered (as the ordering is circular, you can start listing them with any word). If it's impossible, print "Impossible"
susana arbol listo otro orden nexos
The first thing I know is that for finding the ordering you only need two letters (first and last of each word). I was thinking in Hamiltonian Cycle, but the input is too big.