{$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 16384,0,655360}
Program NOIPG2;
Type
    StrType=String[20];
    SType=Array[1..2800] Of Record Name:StrType; Step:Integer; End;
Var
ct:longint absolute $40:$6C;
ot:Longint;{ct和ot为卡时所用变量，相关语句均为卡时所用}
   F:Text;
   Fname:String;
   A,B:StrType;{A为初始状态，B为目标状态}
   Data:Array[1..6,1..2] Of StrType;{变换方案}
   DataC:Integer; {变换方案数}
   S,S2:^SType;{分别为正向和逆向搜索时记录状态的变量}
   Str1:String;{临时变量}
   i,j,P,Head,Rear,Head2,Rear2:Integer;
   IsSame:Boolean;
Begin
assign(output,'string.out');rewrite(output);
fname:='string.in';
ot:=ct;
     New(S); New(S2);
     {读入数据}
     Assign(F,Fname);
     Reset(F);
     ReadLn(F,Str1);
     A:=Copy(Str1,1,Pos(' ',Str1)-1);
     B:=Copy(Str1,Pos(' ',Str1)+1,255);
     DataC:=0;
     While Not Eof(F) Do
     Begin
          Inc(DataC);
          ReadLn(F,Str1);
          Data[DataC,1]:=Copy(Str1,1,Pos(' ',Str1)-1);
          Data[DataC,2]:=Copy(Str1,Pos(' ',Str1)+1,255);
     End;
     Close(F);
 
     {初始化}
     Head:=1; Rear:=2;
     S^[1].Name:=A;
     S^[1].Step:=0;
     Head2:=1; Rear2:=2;
     S2^[1].Name:=B;
     S2^[1].Step:=0;
     {开始搜索}
     Repeat
           if ct-ot>182 then{卡时为10秒}
           begin
                writeln(10);
                halt;
           end;
           {正向搜索}
           If S^[Head].Step>=10 Then
              Break;{“NO ANSWER”的情况}
           For i:=1 To DataC Do
           Begin{按每种方案进行变换}
            P:=0;
             While Pos(Data[i,1],Copy(S^[Head].Name,P+1,255))<>0 Do
             Begin
                P:=Pos(Data[i,1],Copy(S^[Head].Name,P+1,255))+P;
                S^[Rear].Name:=Copy(S^[Head].Name,1,P-1)+Data[i,2]+Copy(S^[Head].Name,P+Length(Data[i,1]),255);
                {判断是否结束}
                IsSame:=False;
                For j:=1 To Rear2-1 Do
                  If S^[Rear].Name=S2^[j].Name Then
                Begin
                     If S^[Head].Step+1+S2^[j].Step<=10 Then
                        WriteLn(S^[Head].Step+1+S2^[j].Step)
                     Else WriteLn('NO ANSWER!');
                     Halt;
                End;
                {判重}
                For j:=1 To Rear-1 Do
                    If S^[Rear].Name=S^[j].Name Then
                    Begin
                         IsSame:=True;
                         Break;
                    End;
                If Not IsSame Then
                Begin
                     S^[Rear].Step:=S^[Head].Step+1;
                     Inc(Rear);
                End;
             End;
           End;
           Inc(Head);
 
           {逆向搜索，基本与上一段程序相同}
           If S2^[Head2].Step>=10 Then
              Break;
           For i:=1 To DataC Do
           Begin
            P:=0;
             While Pos(Data[i,2],Copy(S2^[Head2].Name,P+1,255))<>0 Do
             Begin
                P:=Pos(Data[i,2],Copy(S2^[Head2].Name,P+1,255))+P;
                S2^[Rear2].Name:=Copy(S2^[Head2].Name,1,P-1)+Data[i,1]+Copy(S2^[Head2].Name,P+Length(Data[i,2]),255);
                IsSame:=False;
                For j:=1 To Rear-1 Do
                  If S2^[Rear2].Name=S^[j].Name Then
                Begin
                     If S2^[Head2].Step+1+S^[j].Step<=10 Then
                        WriteLn(S2^[Head2].Step+1+S^[j].Step)
                     Else WriteLn('NO ANSWER!');
                     Halt;
                End;
                For j:=1 To Rear2-1 Do
                    If S2^[Rear2].Name=S2^[j].Name Then
                    Begin
                         IsSame:=True;
                         Break;
                    End;
                If Not IsSame Then
                Begin
                     S2^[Rear2].Step:=S2^[Head2].Step+1;
                     Inc(Rear2);
                End;
             End;
           End;
           Inc(Head2);
     Until (Head>=Rear) Or (Head2>=Rear2);

     WriteLn('NO ANSWER!');
close(output);
End.