#include <vector>
#include <queue>
#include <map>
#include <cstdio>
using namespace std;
#define X 3
#define Y 3
int main(){
	int i=1,start_point;
	vector<int>start(X*Y),goal;
	for(;i<X*Y;i++)goal.push_back(i);goal.push_back(0);
	for(i=0;i<X*Y;i++){
		scanf("%d",&start[i]);
		if(start[i]==0)start_point=i;
	}
	if(start==goal){puts("0");return 0;}

	map<vector<int>,pair<int,int> >mstart;
	queue<vector<int> >q;
	mstart[start]=make_pair(start_point,0);
	q.push(start);
	for(;!q.empty();){
		vector<int> v=q.front();
		q.pop();
		map<vector<int>,pair<int,int> >&m=mstart;
		int coor=m[v].first,x=coor%X,y=coor/X;
		int depth=m[v].second;
		if(0<x){
			swap(v[coor],v[coor-1]);
			if(m.find(v)==m.end())m[v]=make_pair(coor-1,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor-1]);
		}
		if(x<X-1){
			swap(v[coor],v[coor+1]);
			if(m.find(v)==m.end())m[v]=make_pair(coor+1,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor+1]);
		}
		if(0<y){
			swap(v[coor],v[coor-X]);
			if(m.find(v)==m.end())m[v]=make_pair(coor-X,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor-X]);
		}
		if(y<Y-1){
			swap(v[coor],v[coor+X]);
			if(m.find(v)==m.end())m[v]=make_pair(coor+X,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor+X]);
		}
	}
}
### Prompt

Please provide a Cpp coded solution 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 <vector>
#include <queue>
#include <map>
#include <cstdio>
using namespace std;
#define X 3
#define Y 3
int main(){
	int i=1,start_point;
	vector<int>start(X*Y),goal;
	for(;i<X*Y;i++)goal.push_back(i);goal.push_back(0);
	for(i=0;i<X*Y;i++){
		scanf("%d",&start[i]);
		if(start[i]==0)start_point=i;
	}
	if(start==goal){puts("0");return 0;}

	map<vector<int>,pair<int,int> >mstart;
	queue<vector<int> >q;
	mstart[start]=make_pair(start_point,0);
	q.push(start);
	for(;!q.empty();){
		vector<int> v=q.front();
		q.pop();
		map<vector<int>,pair<int,int> >&m=mstart;
		int coor=m[v].first,x=coor%X,y=coor/X;
		int depth=m[v].second;
		if(0<x){
			swap(v[coor],v[coor-1]);
			if(m.find(v)==m.end())m[v]=make_pair(coor-1,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor-1]);
		}
		if(x<X-1){
			swap(v[coor],v[coor+1]);
			if(m.find(v)==m.end())m[v]=make_pair(coor+1,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor+1]);
		}
		if(0<y){
			swap(v[coor],v[coor-X]);
			if(m.find(v)==m.end())m[v]=make_pair(coor-X,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor-X]);
		}
		if(y<Y-1){
			swap(v[coor],v[coor+X]);
			if(m.find(v)==m.end())m[v]=make_pair(coor+X,depth+1),q.push(v);
			if(v==goal){printf("%d\n",depth+1);return 0;}
			swap(v[coor],v[coor+X]);
		}
	}
}
```