#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define N 3

int map[N][N];
int x0,y0;
int lim;
bool check(void){
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(i==N-1&&j==N-1) break;
			if(map[i][j]!=i*N+j+1) return false;
		}
	}
	if(map[N-1][N-1]!=0)return false;
	return true;
}

bool swapping(int x,int y,int dep){
	int temp=map[x0+x][y0+y];
	map[x0+x][y0+y]=map[x0][y0];
	map[x0][y0]=temp;
	x0+=x;
	y0+=y;
	if(check()){
		printf("%d\n",dep);
		exit(0);
		return true;
	}
	if(dep<=lim){
		if(x!=1&&x0-1!=-1) swapping(-1,0,dep+1);
		if(x!=-1&&x0+1!=N) swapping(1,0,dep+1);
		if(y!=1&&y0-1!=-1) swapping(0,-1,dep+1);
		if(y!=-1&&y0+1!=N) swapping(0,1,dep+1);
	}
	temp=map[x0-x][y0-y];
	map[x0-x][y0-y]=map[x0][y0];
	map[x0][y0]=temp;
	x0-=x;
	y0-=y;
	return false;
}
int main(void){
	time_t t;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			scanf("%d",&map[i][j]);
			if(map[i][j]==0){
				x0=i;
				y0=j;
			}
		}
	}
	if(check()){
		printf("0\n");
		return 0;
	}
	time_t t0=time(NULL);
	for(lim=1;lim<46;lim++){
		t=time(NULL);
//		printf("lim:%d:%lld\n",lim,t-t0);
		t0=t;
		if(x0-1!=-1) swapping(-1,0,1);
		if(x0+1!=N) swapping(1,0,1);
		if(y0-1!=-1) swapping(0,-1,1);
		if(y0+1!=N) swapping(0,1,1);
	}
//	printf("Unsolved\n");
	return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 <stdio.h>
#include <time.h>
#include <stdlib.h>
#define N 3

int map[N][N];
int x0,y0;
int lim;
bool check(void){
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(i==N-1&&j==N-1) break;
			if(map[i][j]!=i*N+j+1) return false;
		}
	}
	if(map[N-1][N-1]!=0)return false;
	return true;
}

bool swapping(int x,int y,int dep){
	int temp=map[x0+x][y0+y];
	map[x0+x][y0+y]=map[x0][y0];
	map[x0][y0]=temp;
	x0+=x;
	y0+=y;
	if(check()){
		printf("%d\n",dep);
		exit(0);
		return true;
	}
	if(dep<=lim){
		if(x!=1&&x0-1!=-1) swapping(-1,0,dep+1);
		if(x!=-1&&x0+1!=N) swapping(1,0,dep+1);
		if(y!=1&&y0-1!=-1) swapping(0,-1,dep+1);
		if(y!=-1&&y0+1!=N) swapping(0,1,dep+1);
	}
	temp=map[x0-x][y0-y];
	map[x0-x][y0-y]=map[x0][y0];
	map[x0][y0]=temp;
	x0-=x;
	y0-=y;
	return false;
}
int main(void){
	time_t t;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			scanf("%d",&map[i][j]);
			if(map[i][j]==0){
				x0=i;
				y0=j;
			}
		}
	}
	if(check()){
		printf("0\n");
		return 0;
	}
	time_t t0=time(NULL);
	for(lim=1;lim<46;lim++){
		t=time(NULL);
//		printf("lim:%d:%lld\n",lim,t-t0);
		t0=t;
		if(x0-1!=-1) swapping(-1,0,1);
		if(x0+1!=N) swapping(1,0,1);
		if(y0-1!=-1) swapping(0,-1,1);
		if(y0+1!=N) swapping(0,1,1);
	}
//	printf("Unsolved\n");
	return 0;
}
```