The Problem

We call “chained words” to a sequence of words where each word starts with the last letter of the previous word, except the first one which starts with the last letter of the last word. For example “all lions seek koala” is a list of four chained words.

You have to write a program to find sequences of chained words. It will receive a list of words and it should rearrange them, if possible, to form a chain of words. If more than one chain can be formed, it should show only the first one in lexicographical order.

The Input

The input format is as follows:

An integer in a single line which says the number of problems to solve. Then, for each problem:

• A line with one integer between 2 and 200000 representing the number of words in the text.
• As many words as indicated by the previous integer, separated by any number of spaces or end of line characers (these whitespace characters are only separators and should be ignored). Words contain only lowercase letters and are less than 100 characters long.

The Output

For each problem, a line with the input words reordered to form a chain, separated by one space from each other. If there is no way to form a chain, the line should be “No way”.

Sample Input

2
9
rack car kiosk minumum atom
metal lima arctic kenia
5
star rest type plane east

Sample Output

arctic car rack kiosk kenia atom minumum metal lima
No way

OMP'17
Facultad de Informática
Universidad de Murcia