//h_r_k_s@yahoo.com
//IDS code
#include <conio.h>
#include <iostream.h>

int g[10]={0,1,2,3,4,5,6,7,8,0};//goal
int s[10]={0,3,2,4,5,6,7,8,0,1};//initial state


void IDS(int,int,int);
void init(int [][5],int,int);
void succesor(int ,int );
int goalcheck();
int d=0;
int flag=0;
int arr[2][100];
int r=0;
int t;
void main()
{
	clrscr();
	int l=1;
	while(d==0)
	{
		IDS(1,1,l);
		if(flag==1)
		{
			d=1;
		}
		l++;
	}
	l--;
	cout<<l;
	for(int i=0;i<t;i++)
	{
		cout<<"\n"<<arr[0][i]<<" "<<arr[1][i];
	}
	getch();
}
void IDS(int i,int j,int l)
{
	if(goalcheck()==1)
	{

		l=0;
		flag=1;
		t=r;
		return;
	}
	else if(l>0)
	{
		int sucarray[2][5];
		init(sucarray,j,i);
		int k=0;
		while(sucarray[0][k]!=-1 && flag!=1)
		{
			succesor(sucarray[0][k],sucarray[1][k]);
			arr[0][r]=sucarray[0][k];
			arr[1][r]=sucarray[1][k];
			r++;
			IDS(sucarray[0][k],sucarray[1][k],l-1);
			succesor(sucarray[0][k],sucarray[1][k]);
			k++;
			r--;
		}
		return;
	}
}
void init(int sucarray[][5],int a,int b)
{
	int i=1;
	while(s[i]!=0)
		i++;
	if(i==1)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i+1;//1:2
		sucarray[0][1]=i;
		sucarray[1][1]=i+3;//1:4
		sucarray[0][2]=-1;
	}else if(i==2)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i-1;//2:1
		sucarray[0][1]=i;
		sucarray[1][1]=i+1;//2:3
		sucarray[0][2]=i;
		sucarray[1][2]=i+3;//2:5
		sucarray[0][3]=-1;
	}else if(i==3)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i-1;//3:2
		sucarray[0][1]=i;
		sucarray[1][1]=i+3;//3:6
		sucarray[0][2]=-1;
	}else if(i==4)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i+1;//4:5
		sucarray[0][1]=i;
		sucarray[1][1]=i+3;//4:7
		sucarray[0][2]=i;
		sucarray[1][2]=i-3;//4:1
		sucarray[0][3]=-1;
	}else if(i==5)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i+1;//5:6
		sucarray[0][1]=i;
		sucarray[1][1]=i-1;//5:4
		sucarray[0][2]=i;
		sucarray[1][2]=i-3;//5:2
		sucarray[0][3]=i;
		sucarray[1][3]=i+3;//5:8
		sucarray[0][4]=-1;
	}else if(i==6)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i-3;//6:3
		sucarray[0][1]=i;
		sucarray[1][1]=i-1;//6:5
		sucarray[0][2]=i;
		sucarray[1][2]=i+3;//6:9
		sucarray[0][3]=-1;
	}else if(i==7)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i+1;//7:8
		sucarray[0][1]=i;
		sucarray[1][1]=i-3;//7:4
		sucarray[0][2]=-1;
	}else if(i==8)
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i-1;//8:7
		sucarray[0][1]=i;
		sucarray[1][1]=i+1;//8:9
		sucarray[0][2]=i;
		sucarray[1][2]=i-3;//8:5
		sucarray[0][3]=-1;
	}else
	{
		sucarray[0][0]=i;
		sucarray[1][0]=i-1;//9:8
		sucarray[0][1]=i;
		sucarray[1][1]=i-3;//9:6
		sucarray[0][2]=-1;
	}
	int k=0;
	while(sucarray[0][k]!=-1)
	{
		if(sucarray[1][k]==b)
		{
			for(int v=k;v<4;v++)
			{
				sucarray[0][v]=sucarray[0][v+1];
				sucarray[1][v]=sucarray[1][v+1];
			}
		}
		k++;
	}
}
void succesor(int a,int b)
{
	int temp;
	temp=s[a];
	s[a]=s[b];
	s[b]=temp;
}
int goalcheck()
{
	for(int i=1;i<=9;i++)
	{
		if(s[i]!=g[i])
			return -1;
	}
	return 1;
}