#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

const vector<VI> cnsw ={
	{1,3},  {0,2,4},  {1,5},
	{0,4,6},{1,3,5,7},{2,4,8},
	{3,7},  {4,6,8},  {5,7}
};

const VI pps = {1,2,3,4,5,6,7,8,0};
int main(){
	
	VI ba(9); int wi;
	rep(i,3) rep(j,3) {cin >> wi; ba[i*3+j] = wi;}

	map<VI, int> usd;
	queue<VI> q;
	q.emplace(pps);
	usd[pps] = 0;
	int ct=0;
	while(!q.empty()){
		auto cv = q.front(); q.pop();
		int crz, oc = usd[cv]; 
		rep(i,9) if(cv[i]==0){crz=i; break;}
		for(auto p: cnsw[crz]){
			swap(cv[crz], cv[p]);
			if(!usd.count(cv) ){
				q.emplace(cv);
				usd[cv] = oc +1;
			}
			swap(cv[crz], cv[p]);
		}
	}
	
	
	
	cout << (usd.count(ba)? usd[ba]: -1) <<"\n";
	
	/*for(auto& x: usd){
		cout << x.second <<" :: ";
		for(int z: x.first) cout << z <<" ";
		cout <<"\n";
	}*/
	
	return 0;
}


### Prompt

Please formulate 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>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

const vector<VI> cnsw ={
	{1,3},  {0,2,4},  {1,5},
	{0,4,6},{1,3,5,7},{2,4,8},
	{3,7},  {4,6,8},  {5,7}
};

const VI pps = {1,2,3,4,5,6,7,8,0};
int main(){
	
	VI ba(9); int wi;
	rep(i,3) rep(j,3) {cin >> wi; ba[i*3+j] = wi;}

	map<VI, int> usd;
	queue<VI> q;
	q.emplace(pps);
	usd[pps] = 0;
	int ct=0;
	while(!q.empty()){
		auto cv = q.front(); q.pop();
		int crz, oc = usd[cv]; 
		rep(i,9) if(cv[i]==0){crz=i; break;}
		for(auto p: cnsw[crz]){
			swap(cv[crz], cv[p]);
			if(!usd.count(cv) ){
				q.emplace(cv);
				usd[cv] = oc +1;
			}
			swap(cv[crz], cv[p]);
		}
	}
	
	
	
	cout << (usd.count(ba)? usd[ba]: -1) <<"\n";
	
	/*for(auto& x: usd){
		cout << x.second <<" :: ";
		for(int z: x.first) cout << z <<" ";
		cout <<"\n";
	}*/
	
	return 0;
}


```