Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 1.0 Seconds Memory Limit: 65536K

Total Runs: 420 Accepted Runs: 89

A word ladder is a sequence of words, in which two consecutive words differ by exactly
one letter. An example of such a ladder (usually arranged vertically, hence the "ladder")
would be: *beer*, *brew*, *brow*, *word*, *down*. Note that to get from one word to the next, the letters may be rearranged, and exactly one letter is changed.### Input

On the first line an integer *t* (1 ≤ *t* ≤ 100): the number of test cases. Then for each test case: A line with two space-separated integers *n* (2 ≤ *n* ≤ 100) and *l* (1 ≤ *l* ≤ 20): the number of words and their length.
*n* lines with a word, each consisting of *l* lowercase letters (a - z).
### Output

For each testcase: a single line with the words in a ladder of minimal length, separated by a single space.### Sample Input

### Sample Output

### Notes

If *s* and *t* are strings of equal length and *s*_{i} denotes the *i*-th character of *s*, then *s* precedes *t* lexicographically if for some *i*: *s*_{i} < *t*_{i} and *s*_{j} = *t*_{j} for all *j* < *i*.

For this problem, you will be given a dictionary of distinct words, all of the same length. Your task is to write a program that finds a word ladder of minimal length, such that the first and last word of the ladder have no letters in common.

It is guaranteed that at least one such ladder can be constructed. If there is more than one, output the one that comes first lexicographically.

1 9 3 alt spy sea opt pea ape spa apt ale

ale alt apt opt

Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop