Подразделы

Другие разделы

Дата и время

13/03/2025 15:57:50

Авторизация

Зарегистрироваться
Восстановить пароль

Тренировка 5

A. Word Ladder B. Bonus Word C. Contest D. Cycling E. Escape F. Settling Salesman Problem G. Space H. Herbert

A. Word Ladder

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.

Notes

$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$ .

Sample input

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

Sample output

ale alt apt opt

Source: BAPC preliminary contest, 2007