import java.io.*;

public class Block{
	 public String []blockString;
	 private Block []childBlock;
	 private int access;
	 public Block []route;
	 
	 public Block(String []xBlock){
	 	 this.blockString=new String[xBlock.length];
	 	 for(int i=0;i<xBlock.length;i++)
	 	    blockString[i]=new String(xBlock[i]);
	 	 this.childBlock=new Block[4];
	 	 for(int i=0;i<4;i++)this.childBlock[i]=null;
	 	 access=0;
	 	}  
	 	
	 public boolean createBlockTree(String []yBlock,int dm){
	 	 Block p,q;
	 	 String []xsBlock;
	 	 String []xBlock;
	 	 int d=0,c=0;
	 	 p=this;
	 	 int blockN=(int)Math.sqrt(p.blockString.length);
	 	 while(!complete(p.blockString,yBlock)){
	 	 	 c=0;
	 	 	 p.access=1;
	 	 	 xsBlock=new String[p.blockString.length];
	 	 	 xBlock=new String[p.blockString.length];
	 	 	 for(int i=0;i<p.blockString.length;i++){xsBlock[i]=new String(p.blockString[i]);xBlock[i]=new String(p.blockString[i]);}
	 	 	 switch(stateSpace(xsBlock)){
	 	 	 	 case 0:xBlock[0]=xsBlock[blockN].toString();xBlock[blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[blockN]=xsBlock[blockN].toString();
	 	 	 	        xBlock[0]=xsBlock[1].toString();xBlock[1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[1]=xsBlock[1].toString();	
	 	 	 	        break;	
	 	 	 	 case 1:xBlock[blockN-1]=xsBlock[blockN-2].toString();xBlock[blockN-2]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[blockN-2]=xsBlock[blockN-2].toString();	
	 	 	 	        xBlock[blockN-1]=xsBlock[2*blockN-1].toString();xBlock[2*blockN-1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[2*blockN-1]=xsBlock[2*blockN-1].toString();
	 	 	 	        break;
	 	 	 	 case 2:xBlock[xBlock.length-blockN]=xsBlock[xBlock.length-2*blockN].toString();xBlock[xBlock.length-2*blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[xBlock.length-2*blockN]=xsBlock[xBlock.length-2*blockN].toString();
	 	 	 	        xBlock[xBlock.length-blockN]=xsBlock[xBlock.length-blockN+1].toString();xBlock[xBlock.length-blockN+1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        break;
	 	 	 	 case 3:xBlock[xBlock.length-1]=xsBlock[xBlock.length-2].toString();xBlock[xBlock.length-2]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[xBlock.length-2]=xsBlock[xBlock.length-2].toString();
	 	 	 	        xBlock[xBlock.length-1]=xsBlock[xBlock.length-1-blockN].toString();xBlock[xBlock.length-1-blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        break;
	 	 	 	 case 4:int space=placeSpace(xsBlock);
	 	 	 	        xBlock[space]=xsBlock[space-1].toString();xBlock[space-1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-1]=xsBlock[space-1].toString();
	 	 	 	        xBlock[space]=xsBlock[space+1].toString();xBlock[space+1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+1]=xsBlock[space+1].toString();	
	 	 	 	        xBlock[space]=xsBlock[space+blockN].toString();xBlock[space+blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+blockN]=xsBlock[space+blockN].toString();
	 	 	 	        break;	 	 	 	   
	 	 	 	 case 5:space=placeSpace(xsBlock);
	 	 	 	        xBlock[space]=xsBlock[space+1].toString();xBlock[space+1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+1]=xsBlock[space+1].toString();
	 	 	 	        xBlock[space]=xsBlock[space-blockN].toString();xBlock[space-blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-blockN]=xsBlock[space-blockN].toString();
	 	 	 	        xBlock[space]=xsBlock[space+blockN].toString();xBlock[space+blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+blockN]=xsBlock[space+blockN].toString();	
	 	 	 	        break;
	 	 	 	 case 6:space=placeSpace(xsBlock);
	 	 	 	        xBlock[space]=xsBlock[space-blockN].toString();xBlock[space-blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-blockN]=xsBlock[space-blockN].toString();
	 	 	 	        xBlock[space]=xsBlock[space+blockN].toString();xBlock[space+blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+blockN]=xsBlock[space+blockN].toString();	
	 	 	 	        xBlock[space]=xsBlock[space-1].toString();xBlock[space-1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-1]=xsBlock[space-1].toString();
	 	 	 	        break;
	 	 	 	 case 7:space=placeSpace(xsBlock);
	 	 	 	        xBlock[space]=xsBlock[space-1].toString();xBlock[space-1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-1]=xsBlock[space-1].toString();
	 	 	 	        xBlock[space]=xsBlock[space+1].toString();xBlock[space+1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+1]=xsBlock[space+1].toString();	
	 	 	 	        xBlock[space]=xsBlock[space-blockN].toString();xBlock[space-blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-blockN]=xsBlock[space-blockN].toString();
	 	 	 	        break;
	 	 	 	 case 8:space=placeSpace(xsBlock);
	 	 	 	        xBlock[space]=xsBlock[space-blockN].toString();xBlock[space-blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-blockN]=xsBlock[space-blockN].toString();
	 	 	 	        xBlock[space]=xsBlock[space+blockN].toString();xBlock[space+blockN]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+blockN]=xsBlock[space+blockN].toString();
	 	 	 	        xBlock[space]=xsBlock[space-1].toString();xBlock[space-1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++){if(p.childBlock[i]==null)break;}
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space-1]=xsBlock[space-1].toString();
	 	 	 	        xBlock[space]=xsBlock[space+1].toString();xBlock[space+1]="";
	 	 	 	        if(insertOK(p,xBlock)){
	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+1]=xsBlock[space+1].toString();	
	 	 	 	        break;
	 	 	 	}
	 	 	 int i;	 	 	 	
	 	 	 for(i=0;i<p.length();i++){
	 	 	 	     if(complete(p.childBlock[i].blockString,yBlock)){c=1;break;}
	 	 	 	 	}
	 	 	 if(c==1){d++;System.out.println(d);p=p.childBlock[i];break;}
	 	 	 if((q=findSameLayer(d,this))==null){
	 	 	 	 if(p.length()>0&&(d<dm)){
	 	 	 	 	d++;System.out.println(d);p=p.childBlock[0];
	 	 	 	   }
	 	 	 	 else if((q=findSameLayer(d,this))!=null)p=q;
	 	 	 	 else if(d<dm&&(q=findSameLayer(++d,this))!=null){System.out.println(d);p=q;}
	 	 	 	 else return false;
	 	 	 	}
	 	 	 else p=q;
	 	 	}
	 	 if(complete(p.blockString,yBlock)){
	 	 	this.route=new Block[d+1];
	 	 	for(int i=d;i>=0;i--){
	 	 	  this.route[i]=p;
	 	 	  p=findParent(p,this);
	 	 	 }
	 	 	return true;
	 	   }
	 	 else return false;
	 	}
	 	
	  private Block findSameLayer(int d,Block p){
	  	 Block q;
	  	 int l=0;
	  	 if(d==0&&p.access==0)return p;
	  	 else if(d==0)return null;
	  	 for(int i=0;i<p.length();i++)
	  	    if((q=findSameLayer(d-1,p.childBlock[i]))!=null)return q;
	  	 return null;
	  	}
	 	
	  private boolean complete(String []xBlock,String []yBlock){
	 	 for(int i=0;i<xBlock.length;i++)
	 	   if(!xBlock[i].equals(yBlock[i]))return false;
	 	 return true;   
	    }
	  
	  private int stateSpace(String []xBlock){
	 	 int space=placeSpace(xBlock);
	 	 int blockN=(int)Math.sqrt(xBlock.length);
	 	 if(space==0)return 0;
	 	 if(space==blockN-1)return 1;
	 	 if(space==xBlock.length-blockN)return 2;
	 	 if(space==xBlock.length-1)return 3;
	 	 if(space>0&&space<blockN-1)return 4;
	 	 if(space>xBlock.length-blockN&&space<xBlock.length-1)return 7;
	 	 if(space%blockN==0)return 5;
	 	 if((space+1)%blockN==0)return 6;
	 	 return 8;
	 	}
	 
	 private boolean insertOK(Block p,String []xBlock){
	 	 Block q=p;
	 	 if(complete(q.blockString,xBlock))return false;
	 	 while(!complete(q.blockString,this.blockString)){
	 	 	 q=findParent(q,this);
	 	 	 if(complete(q.blockString,xBlock))return false;
	 	 	}
	 	 return true;	
	 	}
	 private int placeSpace(String []xBlock){
	 	 for(int i=0;i<xBlock.length;i++)
	 	   if(xBlock[i].equals(""))return i;
	 	 return 82;
	 	}
	 	
	 private int length(){
	 	 int i=0;
	 	 while(i<this.childBlock.length&&this.childBlock[i]!=null)i++;
	 	 return i;
	 	}
	 	
	 private Block findParent(Block p,Block q){
	 	 Block x;
	 	 if(q.length()<=0)return null;
	 	 for(int i=0;i<q.length();i++)
	 	   if(q.childBlock[i]==p)return q;
	 	 for(int i=0;i<q.length();i++){
	 	 	 if((x=findParent(p,q.childBlock[i]))!=null)return x;
	 	 	}
	 	 return null;	
	 	}
	 
	 public void displayRoute(){
	 	 System.out.println("The route is");
	 	 for(int i=0;i<this.route.length&&this.route[i]!=null;i++) 
	 	    this.route[i].display();
	 	}
	 
	 public void display(){
	 	 for(int i=0;i<this.blockString.length;i++){
	 	   System.out.print(this.blockString[i]+" ");
	 	   if(this.blockString[i].equals(""))System.out.print(" ");
	 	   if((i+1)%((int)Math.sqrt(this.blockString.length))==0)System.out.println();
	 	  }
	 	 System.out.println();  
	 	}
	 	
	 public int numBlock(){
	 	 return this.blockString.length;
	 	}
	 	
	}
	
class testBlock{
	 public static void main(String args[]){
	 	 Block x;
	 	 boolean t;
	 	 String []xBlock=new String[9];
	 	 String []yBlock=new String[9];
	 	 xBlock[0]="8";xBlock[1]="4";xBlock[2]="7";xBlock[3]="2";xBlock[4]="";
	 	 xBlock[5]="3";xBlock[6]="6";xBlock[7]="1";xBlock[8]="5";
	 	 yBlock[0]="1";yBlock[1]="2";yBlock[2]="3";yBlock[3]="8";yBlock[4]="";
	 	 yBlock[5]="4";yBlock[6]="7";yBlock[7]="6";yBlock[8]="5";   
	 	 x=new Block(xBlock);
	 	 System.out.print((t=x.createBlockTree(yBlock,47)));
	 	 if(t)x.displayRoute();
	 	}
	}