#include <bits/stdc++.h> using namespace std; string a, b, a1, b1; int cnt, pos; string x[10], y[10]; struct T { string s; int step; }; bool find(string s1, string s2,int tt) { int flag; //从tt开始 for(int i=tt;i<s1.size();i++) { flag = 1; for(int j=0;j<s2.size();j++) { if(i+j>=s1.size()||i+j<s1.size()&&s1[i+j]!=s2[j]) { flag = 0; break; } } if(flag==1) { pos = i; return true; } } return false; } int bfs() { set<string>vis; vis.insert(a); queue<T> q; q.push({a,0}); while(q.size()) { T t = q.front(); q.pop(); if(t.step>10) return -1; if(t.s==b) { return t.step; } for(int i=1;i<=cnt;i++) { //从tt开始找,所有的都要替代 int tt=0; while(find(t.s,x[i],tt)) { //下一次从下一个开始 tt=pos+1; string ans=""; //cout<<pos<<"\n"; for(int j=0;j<pos;j++) ans += t.s[j]; ans += y[i]; for(int j=pos+x[i].size();j<t.s.size();j++) ans += t.s[j]; //对操作过的不再查询 if(vis.count(ans))continue; vis.insert(ans); //cout<<ans<<"\n"; q.push({ans,t.step+1}); //printf("%s\n", ans.c_str()); } } } //没有找到也返回-1 return -1; } int main() { // freopen("data1.in","r",stdin); // freopen("data1.out","w",stdout); cin>>a>>b; while(cin>>a1>>b1) { cnt++; x[cnt] = a1; y[cnt] = b1; } int ans = bfs(); if(ans!=-1) printf("%d\n", ans); else printf("NO ANSWER!\n"); return 0; }