1 #include<iostream>
2 #include<stdio.h>
3 #include<set>
4 #include<vector>
5 #include<queue>
6 #include<utility>
7 #include<string>
8 #include<stdlib.h>
9 using namespace std;
10 struct data{string str;int step;};
11 vector<pair<string,string> > v;
12 set<string> s;
13 string a,b,ta,tb,ts;
14 void Search();
15 int main()
16 {
17 cin>>a>>b;
18 while(cin>>ta>>tb)
19 v.push_back(make_pair(ta,tb));
20 Search();
21 }
22 void Search()
23 {
24 data f,p;
25 p.str=a;
26 p.step=0;
27 queue<data> q;
28 q.push(p);
29 while(!q.empty())
30 {
31 f=q.front();
32 if(f.step>10)
33 {
34 printf("NO ANSWER!");
35 exit(0);
36 }
37 for(int i=0;i<v.size();++i)
38 {
39 if(f.str.find(v[i].first)!=-1)
40 {
41 for(int j=f.str.find(v[i].first);j<f.str.length();j=f.str.find(v[i].first,j+1))
42 {
43 ts=f.str;
44 ts.replace(j,v[i].first.length(),v[i].second);
45 if(ts==b)
46 {
47 printf("%d",f.step+1);
48 exit(0);
49 }
50 if(!s.count(ts))
51 {
52 s.insert(ts);
53 p.step=f.step+1;
54 p.str=ts;
55 q.push(p);
56 }
57 }
58 }
59 }
60 q.pop();
61 }
62 printf("NO ANSWER!");
63 exit(0);
64 }