#include<cstdio>
#include<functional>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
int main(void)
{
	int i,j,a[9],b[9],x1,go,g[9]={1,2,3,4,5,6,7,8,0},x2,x3,y,x4;
	int d[9][4]={{1,3,-1,-1},{0,2,4,-1},{1,5,-1,-1},
		{0,4,6,-1},{1,3,5,7},{2,4,8,-1},
	{3,7,-1,-1},{4,6,8,-1},{5,7,-1,-1}};
	set<int> ss;
	set<int>::iterator it;
	queue<int> q1,q2,q3;
	go=0;
	for(i=0;i<9;i++){
		go*=9;
		go+=g[i];
	}
	for(i=0;i<9;i++)	scanf("%d",&a[i]);
	x1=0;
	for(i=0;i<9;i++){
		x1*=9;
		x1+=a[i];
		if(a[i]==0)	x2=i;
	}	
	ss.insert(x1);
	x3=0;
	q1.push(x1);	q2.push(x2);	q3.push(x3);
	while(q1.size()!=0)	{
		x1=q1.front();	q1.pop();
		x2=q2.front();	q2.pop();
		x3=q3.front();	q3.pop();
//		printf("x1=%d\n",x1);
		if(x1==go)	break;
		for(j=8;j>=0;j--)	{
			b[j]=x1%9;
			x1/=9;
		}		
//		for(i=0;i<9;i++)	printf("%d ",b[i]);	printf("\n");
		for(i=0;i<4;i++)	{
			y=d[x2][i];		
//			printf("y=%d\n",y);
			if(y!=-1)	{
				swap(b[x2],b[y]);
				x1=0;
				for(j=0;j<9;j++){
					x1*=9;
					x1+=b[j];
				}	
				it=ss.find(x1);
				if(it==ss.end())	{
					q1.push(x1);	q2.push(y);	q3.push(x3+1);
					ss.insert(x1);
				}
				swap(b[x2],b[y]);
			}
		}
	}
	printf("%d\n",x3);
	return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells where one of the cells is empty space.

In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.


1 3 0
4 2 5
7 8 6


You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).


1 2 3
4 5 6
7 8 0


Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Constraints

* There is a solution.

Input

The $3 \times 3$ integers denoting the pieces or space are given.

Output

Print the fewest steps in a line.

Example

Input

1 3 0
4 2 5
7 8 6


Output

4

### Response

```cpp
#include<cstdio>
#include<functional>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
int main(void)
{
	int i,j,a[9],b[9],x1,go,g[9]={1,2,3,4,5,6,7,8,0},x2,x3,y,x4;
	int d[9][4]={{1,3,-1,-1},{0,2,4,-1},{1,5,-1,-1},
		{0,4,6,-1},{1,3,5,7},{2,4,8,-1},
	{3,7,-1,-1},{4,6,8,-1},{5,7,-1,-1}};
	set<int> ss;
	set<int>::iterator it;
	queue<int> q1,q2,q3;
	go=0;
	for(i=0;i<9;i++){
		go*=9;
		go+=g[i];
	}
	for(i=0;i<9;i++)	scanf("%d",&a[i]);
	x1=0;
	for(i=0;i<9;i++){
		x1*=9;
		x1+=a[i];
		if(a[i]==0)	x2=i;
	}	
	ss.insert(x1);
	x3=0;
	q1.push(x1);	q2.push(x2);	q3.push(x3);
	while(q1.size()!=0)	{
		x1=q1.front();	q1.pop();
		x2=q2.front();	q2.pop();
		x3=q3.front();	q3.pop();
//		printf("x1=%d\n",x1);
		if(x1==go)	break;
		for(j=8;j>=0;j--)	{
			b[j]=x1%9;
			x1/=9;
		}		
//		for(i=0;i<9;i++)	printf("%d ",b[i]);	printf("\n");
		for(i=0;i<4;i++)	{
			y=d[x2][i];		
//			printf("y=%d\n",y);
			if(y!=-1)	{
				swap(b[x2],b[y]);
				x1=0;
				for(j=0;j<9;j++){
					x1*=9;
					x1+=b[j];
				}	
				it=ss.find(x1);
				if(it==ss.end())	{
					q1.push(x1);	q2.push(y);	q3.push(x3+1);
					ss.insert(x1);
				}
				swap(b[x2],b[y]);
			}
		}
	}
	printf("%d\n",x3);
	return 0;
}

```