#include<bits/stdc++.h>
using namespace std;
int x,sx,sy,g[3][3],dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
struct node{
	int v[3][3],x,y,step;
};
map<string,int> ht;
int judge(node a){
	string s="";
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			x=a.v[i][j];
			s+=x+'0';
		}
	}
	if(!ht[s]){
		ht[s]=1;
		return 1;
	}
	else return 0;
}
int check(node a){
	int cnt=1,f=1;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(a.v[i][j]==cnt){
				cnt++;
				if(cnt==9) cnt=0;
			}
			else f=0;
		}
	}
	return f;
}
void bfs(){
	queue<node> q;
	node tmp,tt;
	tmp.x=sx,tmp.y=sy,tmp.step=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			tmp.v[i][j]=g[i][j];
		}
	}
	judge(tmp);
	q.push(tmp);
	while(!q.empty()){
		tt=q.front();
		q.pop();
		if(check(tt)) {
			printf("%d\n",tt.step);
			break;
		}
		for(int i=0;i<4;i++){
			int tx=tt.x+dir[i][0];
			int ty=tt.y+dir[i][1];
			if(tx>=0&&tx<3&&ty>=0&&ty<3){
				tmp.x=tx,tmp.y=ty,tmp.step=tt.step+1;
				for(int i=0;i<3;i++){
					for(int j=0;j<3;j++){
						tmp.v[i][j]=tt.v[i][j];
					}
				}
				tmp.v[tt.x][tt.y]=tt.v[tx][ty];
				tmp.v[tx][ty]=0;
				if(judge(tmp)){
					q.push(tmp);
				}
			}
		}
	} 
}
int main()
{
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			scanf("%d",&x);
			if(x==0) {
				sx=i,sy=j;
			}
			g[i][j]=x;
		}
	}
	bfs();
 } 

### Prompt

Your challenge is to write a cpp solution to the following problem:

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<bits/stdc++.h>
using namespace std;
int x,sx,sy,g[3][3],dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
struct node{
	int v[3][3],x,y,step;
};
map<string,int> ht;
int judge(node a){
	string s="";
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			x=a.v[i][j];
			s+=x+'0';
		}
	}
	if(!ht[s]){
		ht[s]=1;
		return 1;
	}
	else return 0;
}
int check(node a){
	int cnt=1,f=1;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(a.v[i][j]==cnt){
				cnt++;
				if(cnt==9) cnt=0;
			}
			else f=0;
		}
	}
	return f;
}
void bfs(){
	queue<node> q;
	node tmp,tt;
	tmp.x=sx,tmp.y=sy,tmp.step=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			tmp.v[i][j]=g[i][j];
		}
	}
	judge(tmp);
	q.push(tmp);
	while(!q.empty()){
		tt=q.front();
		q.pop();
		if(check(tt)) {
			printf("%d\n",tt.step);
			break;
		}
		for(int i=0;i<4;i++){
			int tx=tt.x+dir[i][0];
			int ty=tt.y+dir[i][1];
			if(tx>=0&&tx<3&&ty>=0&&ty<3){
				tmp.x=tx,tmp.y=ty,tmp.step=tt.step+1;
				for(int i=0;i<3;i++){
					for(int j=0;j<3;j++){
						tmp.v[i][j]=tt.v[i][j];
					}
				}
				tmp.v[tt.x][tt.y]=tt.v[tx][ty];
				tmp.v[tx][ty]=0;
				if(judge(tmp)){
					q.push(tmp);
				}
			}
		}
	} 
}
int main()
{
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			scanf("%d",&x);
			if(x==0) {
				sx=i,sy=j;
			}
			g[i][j]=x;
		}
	}
	bfs();
 } 

```