#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
set<long long> s;
int map1[10][10];
int k[10];
int t;
queue<long long> x,y;
void input(){
	int g=0;
	for(int i=0;i<3;++i){
		for(int j=0;j<3;++j){
			cin>>map1[i][j];
			g=g*10+map1[i][j];
		}
	}
	s.insert(g);
	x.push(g);
	y.push(0);
}
void syf(){
	while(!x.empty()){
		if(x.front()==123456780){
			cout<<y.front()<<endl;
			return;
		}
		int g=x.front(),tot=0,kl=-1;
		while(g!=0){
			if(g%10==0) kl=tot;
			k[tot++]=g%10;
		    g/=10;
		}
		if(kl==-1) {
			kl=tot;
			k[tot++]=0;
		}
		if(kl%3>0){
			t=k[kl];
			k[kl]=k[kl-1];
			k[kl-1]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}
			t=k[kl];
			k[kl]=k[kl-1];
			k[kl-1]=t;
		}
		if(kl%3<2){
			t=k[kl];
			k[kl]=k[kl+1];
			k[kl+1]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}
			t=k[kl];
			k[kl]=k[kl+1];
			k[kl+1]=t;			
		}
		if(kl+3<=8){
			t=k[kl];
			k[kl]=k[kl+3];
			k[kl+3]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}	
			t=k[kl];
			k[kl]=k[kl+3];
			k[kl+3]=t;		
		}
		if(kl-3>=0){
			t=k[kl];
			k[kl]=k[kl-3];
			k[kl-3]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}	
			t=k[kl];
			k[kl]=k[kl-3];
			k[kl-3]=t;			
		}
		x.pop();
		y.pop();
	}
}
int main(){
	input();
	syf();
	return 0;
}
### Prompt

Your task is to create 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<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
set<long long> s;
int map1[10][10];
int k[10];
int t;
queue<long long> x,y;
void input(){
	int g=0;
	for(int i=0;i<3;++i){
		for(int j=0;j<3;++j){
			cin>>map1[i][j];
			g=g*10+map1[i][j];
		}
	}
	s.insert(g);
	x.push(g);
	y.push(0);
}
void syf(){
	while(!x.empty()){
		if(x.front()==123456780){
			cout<<y.front()<<endl;
			return;
		}
		int g=x.front(),tot=0,kl=-1;
		while(g!=0){
			if(g%10==0) kl=tot;
			k[tot++]=g%10;
		    g/=10;
		}
		if(kl==-1) {
			kl=tot;
			k[tot++]=0;
		}
		if(kl%3>0){
			t=k[kl];
			k[kl]=k[kl-1];
			k[kl-1]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}
			t=k[kl];
			k[kl]=k[kl-1];
			k[kl-1]=t;
		}
		if(kl%3<2){
			t=k[kl];
			k[kl]=k[kl+1];
			k[kl+1]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}
			t=k[kl];
			k[kl]=k[kl+1];
			k[kl+1]=t;			
		}
		if(kl+3<=8){
			t=k[kl];
			k[kl]=k[kl+3];
			k[kl+3]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}	
			t=k[kl];
			k[kl]=k[kl+3];
			k[kl+3]=t;		
		}
		if(kl-3>=0){
			t=k[kl];
			k[kl]=k[kl-3];
			k[kl-3]=t;
			long long ss=0;
			for(int i=tot-1;i>=0;--i){
				ss=ss*10+k[i];
			}
			if(s.count(ss)==0){
				x.push(ss);
				y.push(y.front()+1);
				s.insert(ss);
			}	
			t=k[kl];
			k[kl]=k[kl-3];
			k[kl-3]=t;			
		}
		x.pop();
		y.pop();
	}
}
int main(){
	input();
	syf();
	return 0;
}
```