program project1;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes
  { you can add units after this };

{$R *.res}

const
  n = 6;
  maxn = 10000;

type node = record
            s:string;
            parent:integer;
            dep:integer;
            method:integer;
            end;
     bin = 0..1;
var
  src,dst:string;
  a,b:array[1..n] of string;
  c:integer;
  i:integer;
  status:array[0..1, 1..maxn] of node;
  front:array[0..1] of integer;
  rear:array[0..1] of integer;
  found:boolean;


procedure init;
begin
  readln(src);
  readln(dst);
  c := 0;

  while not eof do
    begin
      while not eoln do
        begin
          inc(c);
          readln(a[c]);
          readln(b[c]);
        end;
      readln;
    end;

  status[0,1].s := src;
  status[0,1].dep := 0;
  status[0,1].parent := 0;
  status[0,1].method := 0;
  status[1,1].s := dst;
  status[1,1].dep := 0;
  status[1,1].parent := 0;
  status[1,1].method := 0;
  front[0] := 1;rear[0]:= 2;
  front[1] := 1; rear[1]:= 2;
  found:=false;

end;

function check(st:bin):boolean;
var
  i:integer;
begin
  for i := 1 to rear[st] - 1 do
    begin
      if status[st, i].s = status[st, rear[st]].s then
        begin
          check:=false;
          exit;
        end;
    end;
  check:=true;
end;

procedure print(st:bin;tail,k:integer);
procedure print0(m:integer);
begin
  if m = 1 then exit;

  print0(status[0,m].parent);
  write(status[0,m].method);
end;
procedure print1(m:integer);
begin

  while m <> 1 do
  begin
    write(status[1,m].method);
    m:=status[1,m].parent;
  end;
end;

begin
  if st = 0 then
    begin
      writeln('steps:',status[0,tail].dep + status[1,k].dep);

      print0(tail);

      print1(k);
    end
  else
    begin
      writeln('steps:',status[1,tail].dep + status[0,k].dep);

      print0(k);

      print1(tail);
    end;
end;


procedure find(st:bin);
var
  i:integer;
begin
  for i := 1 to rear[1-st]-1 do
    begin
      if status[st, rear[st]].s = status[1-st,i].s then
        begin
          print(st, rear[st],i);
          found:=true;

        end;
    end;
end;

procedure expand(st:bin);
var
  tmpstatus,newstatus:node;
  i:integer;
  p:integer;
  len:integer;

begin
  tmpstatus := status[st, front[st]];

  for i := 1 to c do
    begin
      if st = 0  then
        begin
         p := pos(a[i], tmpstatus.s);
         len := length(a[i]);
        end
      else
        begin
          p := pos(b[i], tmpstatus.s) ;
          len := length(b[i]);
        end;

      if p <> 0 then
        begin
          newstatus := tmpstatus;
          delete(newstatus.s, p, len);

          if st = 0 then
            insert(b[i], newstatus.s, p)
          else
            insert(a[i], newstatus.s, p);

          inc(newstatus.dep);
          newstatus.method:=i;
          newstatus.parent:=front[st];

          status[st,rear[st]]:=newstatus;
          if check(st) then
            begin
              find(st);
              inc(rear[st]);

            end;

        end;
    end;
  inc(front[st]);
end;

begin
  assign(input, 'D:\UVa\uva_in.txt');
  reset(input);

  assign(output, 'D:\UVa\uva_out.txt');
  rewrite(output);


  init;
  {
  writeln(src, ' ', dst);
  writeln('c=',c);
  for i := 1 to c do
    writeln(a[i], ' ', b[i]);
  }

  find(1);

  repeat
    if (rear[0] <= rear[1]) and not ((front[0] >= rear[0]) or (rear[0] > maxn)) then expand(0);
    if (rear[1] <= rear[0]) and not ((front[1] >= rear[1]) or (rear[1] > maxn)) then expand(1);
    if not ((front[0] >= rear[0]) or (rear[0] > maxn)) then expand(0);
    if not ((front[1] >= rear[1]) or (rear[1] > maxn)) then expand(1);
  until (found = true) or (status[0,front[0]].dep + status[1,front[1]].dep > 10) or (((front[0] >= rear[0]) or (rear[0] > maxn)) and ((front[1] >= rear[1]) or (rear[1] > maxn)));

  if not found then
    writeln('No solution');
  readln;
end.