단어 사다리

단어 사다리는 이웃한 두 단어가 글자 하나만 다른 단어의 나열이다. 다음 단어로 넘어갈 때 글자를 원하는 대로 재배열할 수 있고, 그렇게 맞춘 상태에서 정확히 한 글자를 바꾼다. 예를 들어 beer, brew, brow, word, down은 사다리다. 보통 세로로 늘어놓고 읽어서 사다리라고 부른다.

길이가 모두 같고 서로 다른 단어로 이루어진 사전이 주어진다. 사전에 있는 단어만 써서 사다리를 만들 때, 첫 단어와 마지막 단어에 공통으로 들어간 글자가 하나도 없으면서 길이가 가장 짧은 사다리를 찾는 프로그램을 작성하라.

길이가 $l$인 두 단어가 이웃하는 조건은 두 단어의 글자 다중집합이 정확히 $l-1$개의 글자를 공유하는 것과 같다. beer와 brew는 b, e, r을 공유하므로 이웃한다.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다. ($1 \le t \le 100$)

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 단어의 개수 $n$과 단어의 길이 $l$이 공백을 사이에 두고 주어진다. ($2 \le n \le 100$, $1 \le l \le 20$)
• 다음 $n$개 줄에 단어가 한 개씩 주어진다. 단어는 a부터 z까지의 알파벳 소문자로만 이루어진 길이 $l$의 문자열이고, 같은 단어가 두 번 주어지지 않는다.

각 테스트 케이스마다 한 줄에 가장 짧은 사다리를 이루는 단어를 순서대로, 공백 하나로 구분해 출력한다.

조건을 만족하는 사다리는 적어도 하나 존재한다. 가장 짧은 사다리가 여러 개라면 사다리를 이루는 단어를 앞에서부터 차례로 비교해 사전순으로 가장 앞서는 것을 출력한다.

길이가 같은 두 문자열 $s$와 $t$에서 $s_i$가 $s$의 $i$번째 글자를 뜻할 때, 어떤 $i$에 대해 $s_i < t_i$이고 $j < i$인 모든 $j$에 대해 $s_j = t_j$이면 $s$가 $t$보다 사전순으로 앞선다.