记录编号	38998	评测结果	AAAAAAAAAA
题目名称	基因重组	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.884 s
提交时间	2012-07-03 13:15:52	内存使用	50.24 MiB

const q=9876543;
var
 h,t,n,p,tot:longint; a:array[0..q] of longint;
 v:array[0..500000] of string[13];
 f,step,next:array[0..500000] of longint;
 x,s1,s2:string[13]; ch:char;
 num:array['A'..'Z'] of longint;
 procedure init;
 var i:longint;
 begin
  p:=0;
  for i:=1 to length(x) do
   p:=(p*10+num[x[i]]) mod q;
  p:=p mod q;
  p:=(1 shl n*num[x[1]]+1 shl (2*n)*num[x[length(x)]]+p)
   mod q;
  i:=a[p];
  while i<>0 do
   begin
    if v[i]=x then exit;
    i:=next[i];
   end;
  inc(tot); next[tot]:=a[p]; a[p]:=tot; v[tot]:=x;
  inc(t); f[t]:=tot; step[t]:=step[h]+1;
  if x=s2 then
   begin writeln(step[t]);
         close(input); close(output);
         halt;
   end;
 end;
 procedure bfs;
 begin
  fillchar(f,sizeof(f),0);
  h:=0; t:=0; step[0]:=-1; x:=s1;
  init;
  repeat
   inc(h);
   x:=v[f[h]];
   x:=x+x[1];
   delete(x,1,1);
   init;
   x:=v[f[h]];
   ch:=x[1]; x[1]:=x[2]; x[2]:=ch;
   init;
  until h=t;
 end;
begin
 assign(input,'genea.in'); reset(input);
 assign(output,'genea.out'); rewrite(output);
 num['A']:=1; num['T']:=2; num['C']:=3; num['G']:=4;
 readln(n);
 readln(s1);
 readln(s2);
 if s1=s2 then
  begin
   writeln(0);
   close(input); close(output);
   halt;
  end else bfs;
end.