#include<bits/stdc++.h>
using namespace std;
struct itemq
{
string w;
int l;
};
int min(int x, int y, int z)
{
return min(min(x, y), z);
}
int lev(string str1 , string str2 , int m ,int n)
{
if (m == 0)
return n;
if (n == 0)
return m;
if (str1[m-1] == str2[n-1])
return lev(str1, str2, m-1, n-1);
return 1 + min ( lev(str1, str2, m, n-1), // Insert
lev(str1, str2, m-1, n), // Remove
lev(str1, str2, m-1, n-1) // Replace
);
}
bool adj(string& a, string& b)
{
if(lev(a,b,a.size(),b.size())==1)
return true;
else
return false;
}
int ans(string& start, string& end, set<string> &D)
{
if(start==end)
return 1;
queue<itemq> Q;
itemq item = {start, 1};
Q.push(item);
//D.erase(start);
while (!Q.empty())
{
itemq curr = Q.front();
Q.pop();
set<string>::iterator it;
for (it = D.begin(); it != D.end(); it++)
{
cout<<curr.w<<" "<<*it<<endl;
string temp = *it;
if (adj(curr.w, temp))
{
item.w = temp;
item.l = curr.l + 1;
Q.push(item);
D.erase(temp);
if (temp == end)
return item.l;
}
}
}
return -1;
}
int main(void)
{
string s;
set<string> D;
cin>>s;
while(s!="END")
{
D.insert(s);
cin>>s;
}
string start;
cin>>start;
string end;
cin>>end;
set<string>::iterator it;
for (it = D.begin(); it != D.end(); it++)
cout<<*it<<endl;
int cou = ans(start, end, D);
cout << cou <<endl;
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4gCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgaXRlbXEgCnsgCiAgICBzdHJpbmcgdzsgCiAgICBpbnQgbDsgCn07CmludCBtaW4oaW50IHgsIGludCB5LCBpbnQgeikgCnsgCiAgIHJldHVybiBtaW4obWluKHgsIHkpLCB6KTsgCn0gCiAgCmludCBsZXYoc3RyaW5nIHN0cjEgLCBzdHJpbmcgc3RyMiAsIGludCBtICxpbnQgbikgCnsgCiAgICBpZiAobSA9PSAwKSAKICAgIAlyZXR1cm4gbjsgCiAgICBpZiAobiA9PSAwKSAKICAgIAlyZXR1cm4gbTsgCiAgICBpZiAoc3RyMVttLTFdID09IHN0cjJbbi0xXSkgCiAgICAgICAgcmV0dXJuIGxldihzdHIxLCBzdHIyLCBtLTEsIG4tMSk7IAogICAgcmV0dXJuIDEgKyBtaW4gKCBsZXYoc3RyMSwgIHN0cjIsIG0sIG4tMSksICAgIC8vIEluc2VydCAKICAgICAgICAgICAgICAgICAgICAgbGV2KHN0cjEsICBzdHIyLCBtLTEsIG4pLCAgIC8vIFJlbW92ZSAKICAgICAgICAgICAgICAgICAgICAgbGV2KHN0cjEsICBzdHIyLCBtLTEsIG4tMSkgLy8gUmVwbGFjZSAKICAgICAgICAgICAgICAgICAgICk7IAp9IApib29sIGFkaihzdHJpbmcmIGEsIHN0cmluZyYgYikgCnsgCiAgICBpZihsZXYoYSxiLGEuc2l6ZSgpLGIuc2l6ZSgpKT09MSkKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIGVsc2UKICAgICAgICByZXR1cm4gZmFsc2U7Cn0gCmludCBhbnMoc3RyaW5nJiBzdGFydCwgc3RyaW5nJiBlbmQsIHNldDxzdHJpbmc+ICZEKSAKeyAKICAgIGlmKHN0YXJ0PT1lbmQpCiAgICAgICAgcmV0dXJuIDE7CiAgICBxdWV1ZTxpdGVtcT4gUTsgCiAgICBpdGVtcSBpdGVtID0ge3N0YXJ0LCAxfTsKICAgIFEucHVzaChpdGVtKTsgCgkvL0QuZXJhc2Uoc3RhcnQpOwogICAgd2hpbGUgKCFRLmVtcHR5KCkpIAogICAgewogICAgICAgIGl0ZW1xIGN1cnIgPSBRLmZyb250KCk7IAogICAgICAgIFEucG9wKCk7CiAgICAgICAgc2V0PHN0cmluZz46Oml0ZXJhdG9yIGl0OwogICAgICAgIGZvciAoaXQgPSBELmJlZ2luKCk7IGl0ICE9IEQuZW5kKCk7IGl0KyspIAogICAgICAgIHsgCiAgICAgICAgCWNvdXQ8PGN1cnIudzw8IiAiPDwqaXQ8PGVuZGw7CiAgICAgICAgICAgIHN0cmluZyB0ZW1wID0gKml0OyAKICAgICAgICAgICAgaWYgKGFkaihjdXJyLncsIHRlbXApKSAKICAgICAgICAgICAgeyAKICAgICAgICAgICAgCQogICAgICAgICAgICAgICAgaXRlbS53ID0gdGVtcDsgCiAgICAgICAgICAgICAgICBpdGVtLmwgPSBjdXJyLmwgKyAxOyAKICAgICAgICAgICAgICAgIFEucHVzaChpdGVtKTsKICAgICAgICAgICAgICAgIEQuZXJhc2UodGVtcCk7IAogICAgICAgICAgICAgICAgaWYgKHRlbXAgPT0gZW5kKSAKICAgICAgICAgICAgICAgICAgcmV0dXJuIGl0ZW0ubDsgCiAgICAgICAgICAgIH0gCiAgICAgICAgfSAKICAgIH0KICAgIHJldHVybiAtMTsgCn0gCmludCBtYWluKHZvaWQpIAp7IAogICAgc3RyaW5nIHM7CiAgICBzZXQ8c3RyaW5nPiBEOwogICAgY2luPj5zOwogICAgd2hpbGUocyE9IkVORCIpCiAgICB7CiAgICAgICAgRC5pbnNlcnQocyk7CiAgICAgICAgY2luPj5zOwogICAgfQogICAgc3RyaW5nIHN0YXJ0OwogICAgY2luPj5zdGFydDsKICAgIHN0cmluZyBlbmQ7CiAgICBjaW4+PmVuZDsKICAgIHNldDxzdHJpbmc+OjppdGVyYXRvciBpdDsKICAgIGZvciAoaXQgPSBELmJlZ2luKCk7IGl0ICE9IEQuZW5kKCk7IGl0KyspIAogICAgCWNvdXQ8PCppdDw8ZW5kbDsKICAgIGludCBjb3UgPSBhbnMoc3RhcnQsIGVuZCwgRCk7CiAgICBjb3V0IDw8IGNvdSA8PGVuZGw7ICAKICAgIHJldHVybiAwOyAgCn0=