#include <bits/stdc++.h>
using namespace std;

int main()
{
	vector<int> ans = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
	vector<int> s(9);
	for (int i = 0; i < 9; i++) {
		cin >> s[i];
	}
	map<vector<int>, int> mp; mp[s] = 1;
	queue<vector<int>> q; q.push(s);
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		if (p == ans) {
			cout << mp[p] - 1 << endl;
			break;
		}
		int zero;
		for (int i = 0; i < 9; i++) {
			if (p[i] == 0) {
				zero = i;
				break;
			}
		}
		auto cp = p;
		if ((zero + 1) % 3 != 0) {
			swap(cp[zero], cp[zero + 1]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero + 1]);
		}
		if (zero % 3 != 0) {
			swap(cp[zero], cp[zero - 1]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero - 1]);
		}
		if (zero < 6) {
			swap(cp[zero], cp[zero + 3]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero + 3]);
		}
		if (zero >= 3) {
			swap(cp[zero], cp[zero - 3]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero - 3]);
		}
	}
	return 0;
}
### Prompt

Create a solution in Cpp for 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>
using namespace std;

int main()
{
	vector<int> ans = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
	vector<int> s(9);
	for (int i = 0; i < 9; i++) {
		cin >> s[i];
	}
	map<vector<int>, int> mp; mp[s] = 1;
	queue<vector<int>> q; q.push(s);
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		if (p == ans) {
			cout << mp[p] - 1 << endl;
			break;
		}
		int zero;
		for (int i = 0; i < 9; i++) {
			if (p[i] == 0) {
				zero = i;
				break;
			}
		}
		auto cp = p;
		if ((zero + 1) % 3 != 0) {
			swap(cp[zero], cp[zero + 1]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero + 1]);
		}
		if (zero % 3 != 0) {
			swap(cp[zero], cp[zero - 1]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero - 1]);
		}
		if (zero < 6) {
			swap(cp[zero], cp[zero + 3]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero + 3]);
		}
		if (zero >= 3) {
			swap(cp[zero], cp[zero - 3]);
			if (mp[cp] == 0) {
				mp[cp] = mp[p] + 1;
				q.push(cp);
			}
			swap(cp[zero], cp[zero - 3]);
		}
	}
	return 0;
}
```