#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <cassert>
using namespace std;
const int num = 9, ud[] = { -1, 0, 1, 0 }, lr[] = { 0, -1, 0, 1 }, nd = 3;
const char wa[] = { 'u', 'l', 'd', 'r' };
struct puzzle {
	int sp, p[num];
	string way;
	bool operator < (const puzzle &pu) const {
		for (int i = 0; i < num; i++) {
			if (p[i] == pu.p[i]) continue;
			return p[i] < pu.p[i];
		}
		return false;
	}
};
inline bool fin(puzzle pu) {
	for (int i = 0; i < num; i++)
		if (pu.p[i] != i + 1) return false;
	return true;
}
inline string bfs(puzzle pu) {
	queue<puzzle> q;
	map <puzzle, bool> m;
	q.push(pu);
	m[pu] = true;
	puzzle x, y;
	int row, col, ns, ro, co;
	while (!q.empty()) {
		x = q.front(); q.pop();
		if (fin(x)) return x.way;
		ro = x.sp / nd;
		co = x.sp % nd;
		for (int i = 0; i < 4; i++) {
			row = ro + ud[i];
			col = co + lr[i];
			if (row >= nd || row < 0 || col >= nd || col < 0) continue;
			y = x;
			ns = row*nd + col;
			swap(y.p[x.sp], y.p[ns]);
			y.sp = ns;
			if (!m[y]) {
				m[y] = true;
				y.way += wa[i];
				q.push(y);
			}
		}
	}
}
int main() {
	puzzle fi;
	for (int i = 0; i < num; i++) {
		cin >> fi.p[i];
		if (!fi.p[i]) { 
			fi.sp = i; 
			fi.p[i] = num;
		}
	}
	cout << bfs(fi).size() << endl;
	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
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <cassert>
using namespace std;
const int num = 9, ud[] = { -1, 0, 1, 0 }, lr[] = { 0, -1, 0, 1 }, nd = 3;
const char wa[] = { 'u', 'l', 'd', 'r' };
struct puzzle {
	int sp, p[num];
	string way;
	bool operator < (const puzzle &pu) const {
		for (int i = 0; i < num; i++) {
			if (p[i] == pu.p[i]) continue;
			return p[i] < pu.p[i];
		}
		return false;
	}
};
inline bool fin(puzzle pu) {
	for (int i = 0; i < num; i++)
		if (pu.p[i] != i + 1) return false;
	return true;
}
inline string bfs(puzzle pu) {
	queue<puzzle> q;
	map <puzzle, bool> m;
	q.push(pu);
	m[pu] = true;
	puzzle x, y;
	int row, col, ns, ro, co;
	while (!q.empty()) {
		x = q.front(); q.pop();
		if (fin(x)) return x.way;
		ro = x.sp / nd;
		co = x.sp % nd;
		for (int i = 0; i < 4; i++) {
			row = ro + ud[i];
			col = co + lr[i];
			if (row >= nd || row < 0 || col >= nd || col < 0) continue;
			y = x;
			ns = row*nd + col;
			swap(y.p[x.sp], y.p[ns]);
			y.sp = ns;
			if (!m[y]) {
				m[y] = true;
				y.way += wa[i];
				q.push(y);
			}
		}
	}
}
int main() {
	puzzle fi;
	for (int i = 0; i < num; i++) {
		cin >> fi.p[i];
		if (!fi.p[i]) { 
			fi.sp = i; 
			fi.p[i] = num;
		}
	}
	cout << bfs(fi).size() << endl;
	return 0;
}
```