//By Vlgd
#include<bits/stdc++.h>
using namespace std;
const int N=3,NN=9;
const int dx[4]={0,1,-1,0};
const int dy[4]={1,0,0,-1};
struct Puz{
	int mp[NN],space,path;
	bool operator<(const Puz &p)const{
		for(int i=0;i<NN;i++){
			if(mp[i]==p.mp[i]) continue;
			return mp[i]>p.mp[i];
		}
		return false;
	}	
};
bool solved(Puz p){
	for(int i=0;i<NN;i++) if(p.mp[i]!=(i+1)) return false;
	return true;
}
int bfs(Puz s){
	map<Puz,bool>tab;
	queue<Puz>Q;
	Puz u,v;
	s.path=0;
	tab[s]=true;
	Q.push(s);
	while(!Q.empty()){
		u=Q.front();Q.pop();
		if(solved(u)) return u.path;
		int sx=u.space/N,sy=u.space%N;
		for(int i=0;i<4;i++){
			int tx=sx+dx[i],ty=sy+dy[i];
			v=u;
			if(tx<0||ty<0||tx>=N||ty>=N) continue;
			swap(v.mp[u.space],v.mp[tx*N+ty]);
			v.space=tx*N+ty;
			if(!tab[v]){
				v.path++;
				tab[v]=true;
				Q.push(v);
			}
		}
	}
}

int main(){
	Puz src;
	for(int i=0;i<NN;i++){
		scanf("%d",&src.mp[i]);
		if(src.mp[i]==0){
			src.mp[i]=NN;
			src.space=i;
		}
	}
	printf("%d\n",bfs(src));
	return 0;
}

### Prompt

Generate 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
//By Vlgd
#include<bits/stdc++.h>
using namespace std;
const int N=3,NN=9;
const int dx[4]={0,1,-1,0};
const int dy[4]={1,0,0,-1};
struct Puz{
	int mp[NN],space,path;
	bool operator<(const Puz &p)const{
		for(int i=0;i<NN;i++){
			if(mp[i]==p.mp[i]) continue;
			return mp[i]>p.mp[i];
		}
		return false;
	}	
};
bool solved(Puz p){
	for(int i=0;i<NN;i++) if(p.mp[i]!=(i+1)) return false;
	return true;
}
int bfs(Puz s){
	map<Puz,bool>tab;
	queue<Puz>Q;
	Puz u,v;
	s.path=0;
	tab[s]=true;
	Q.push(s);
	while(!Q.empty()){
		u=Q.front();Q.pop();
		if(solved(u)) return u.path;
		int sx=u.space/N,sy=u.space%N;
		for(int i=0;i<4;i++){
			int tx=sx+dx[i],ty=sy+dy[i];
			v=u;
			if(tx<0||ty<0||tx>=N||ty>=N) continue;
			swap(v.mp[u.space],v.mp[tx*N+ty]);
			v.space=tx*N+ty;
			if(!tab[v]){
				v.path++;
				tab[v]=true;
				Q.push(v);
			}
		}
	}
}

int main(){
	Puz src;
	for(int i=0;i<NN;i++){
		scanf("%d",&src.mp[i]);
		if(src.mp[i]==0){
			src.mp[i]=NN;
			src.space=i;
		}
	}
	printf("%d\n",bfs(src));
	return 0;
}

```