```cpp
#include<bits/stdc++.h>
using namespace std;
string bes,ens;
string a[1000],b[1000];
map<string,int> mp;
int len=0,ans=0;
struct node{string s;int step;};
string find(string s,int i,int j)
{
string ans="";
if(i+a[j].size()>s.size()) return ans;
for(int k=0;k<a[j].size();k++)
if(s[i+k]!=a[j][k]) return ans;
ans=s.substr(0,i);
ans+=b[j];
ans+=s.substr(i+a[i].size());
return ans;
}
void bfs()
{
queue<node>p;
node q;
q.s=bes;
q.step=0;
p.push(q);
while(!p.empty()){
node t;
t=p.front();
p.pop();
if(t.s==ens) {ans=t.step;break;}
if(t.step>10) break;
if(mp.count(t.s)==1) continue;
mp[t.s]=1;
for(int i=0;i<t.s.size();i++)
for(int j=1;j<len;j++)
{
node kk;
kk.s=find(t.s,i,j);
if(kk.s!=""){
kk.step=t.step+1;
p.push(kk);
}
}
}
if(ans>10 || ans==0) printf("NO ANSWER!");
else printf("%d\n",ans);
}
int main()
{
cin>>bes>>ens;
while(cin>>a[len]>>b[len]) len++;
bfs();
return 0;
}
```
by PerfectJames @ 2019-02-21 13:37:58