#include <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
#define _all(arg) begin(arg),end(arg)

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0; }
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0; }

using namespace std;
using vi=vector<int>;
using vii=vector<vi>;

map<vii, int> memo;

bool check(vii m) {
	rep(i, 8) {
		if(m[i/3][i%3] != i+1) return false;
	}
	if(m[2][2] != 0) return false;
	return true;
}

int bfs(vii m) {
	queue<vii> Q;
	Q.push(m);
	memo[m] = 0;
	while(Q.size()) {
		vii cur = Q.front();
		Q.pop();

		if(check(cur)) return memo[cur];

		const int dr[4] = {1, 0, -1, 0};
		const int dc[4] = {0, 1, 0, -1};

		int zero_r, zero_c;

		rep(i, 3) rep(j, 3) if(cur[i][j] == 0) zero_r = i, zero_c = j;
		rep(i, 4) {
			vii next = cur;
			int nr = zero_r + dr[i];
			int nc = zero_c + dc[i];
			if(nr<0 || 3<=nr || nc<0 || 3<=nc) continue;
			swap(next[zero_r][zero_c], next[nr][nc]);
			if(memo.find(next) != memo.end()) continue;
			memo[next] = memo[cur]+1;
			Q.push(next);
		}
	}
} 

int main(void){
	vii m(3, vi(3, 0));
	rep(i, 9) cin >> m[i/3][i%3];

	cout << bfs(m) << endl;

	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
#define _all(arg) begin(arg),end(arg)

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0; }
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0; }

using namespace std;
using vi=vector<int>;
using vii=vector<vi>;

map<vii, int> memo;

bool check(vii m) {
	rep(i, 8) {
		if(m[i/3][i%3] != i+1) return false;
	}
	if(m[2][2] != 0) return false;
	return true;
}

int bfs(vii m) {
	queue<vii> Q;
	Q.push(m);
	memo[m] = 0;
	while(Q.size()) {
		vii cur = Q.front();
		Q.pop();

		if(check(cur)) return memo[cur];

		const int dr[4] = {1, 0, -1, 0};
		const int dc[4] = {0, 1, 0, -1};

		int zero_r, zero_c;

		rep(i, 3) rep(j, 3) if(cur[i][j] == 0) zero_r = i, zero_c = j;
		rep(i, 4) {
			vii next = cur;
			int nr = zero_r + dr[i];
			int nc = zero_c + dc[i];
			if(nr<0 || 3<=nr || nc<0 || 3<=nc) continue;
			swap(next[zero_r][zero_c], next[nr][nc]);
			if(memo.find(next) != memo.end()) continue;
			memo[next] = memo[cur]+1;
			Q.push(next);
		}
	}
} 

int main(void){
	vii m(3, vi(3, 0));
	rep(i, 9) cin >> m[i/3][i%3];

	cout << bfs(m) << endl;

	return 0;
}
```