Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2925.   Word Ladder
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.

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.

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.

    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.

    Sample Input

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

    Sample Output

    ale alt apt opt

    Notes

    If s and t are strings of equal length and si denotes the i-th character of s, then s precedes t lexicographically if for some i: si < ti and sj = tj for all j < i.


  • Source: TJU Team Selection Contest 2008 (1)
    Submit   List    Runs   Forum   Statistics

    Tianjin University Online Judge v1.3.0
    Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop