#include <iostream>
#include <queue>
#include <map>
using namespace std;

struct pz{
	int a[9];
	int t;

	bool operator < (const pz &p) const {
		for (int i = 0; i < 9; i++) {
			if (a[i] == p.a[i])
				continue;
			return a[i] > p.a[i];
		}
		return false;
	}
};

int main()
{
	pz p;
	int n = -1;
	map<pz, bool> v;

	for (int i = 0; i < 9; i++)
		cin >> p.a[i];

	p.t = 0;

	queue<pz> que;
	que.push(p);
	v[p] = true;

	while (!que.empty()) {
		pz g = que.front();
		que.pop();

		bool f = 1;

		for (int i = 0; i < 8; i++) {
			if (g.a[i] != (i + 1)) {
				f = 0;
				break;
			}
		}

		if (f == 1) {
			n = g.t;
			break;
		}

		for (int i = 0; i < 9; i++) {
			if (g.a[i] == 0) {
				if(i % 3 != 0){
					g.t++;
					swap(g.a[i], g.a[i - 1]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i - 1]);
					g.t--;
				}
				if (i % 3 != 2) {
					g.t++;
					swap(g.a[i], g.a[i + 1]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i + 1]);
					g.t--;
				}
				if (i / 3 != 0) {
					g.t++;
					swap(g.a[i], g.a[i - 3]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i - 3]);
					g.t--;
				}
				if (i / 3 != 2) {
					g.t++;
					swap(g.a[i], g.a[i + 3]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i + 3]);
					g.t--;
				}
			}
		}
	}

	cout << n << endl;

	return 0;
}

### Prompt

Please create a solution in cpp 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 <queue>
#include <map>
using namespace std;

struct pz{
	int a[9];
	int t;

	bool operator < (const pz &p) const {
		for (int i = 0; i < 9; i++) {
			if (a[i] == p.a[i])
				continue;
			return a[i] > p.a[i];
		}
		return false;
	}
};

int main()
{
	pz p;
	int n = -1;
	map<pz, bool> v;

	for (int i = 0; i < 9; i++)
		cin >> p.a[i];

	p.t = 0;

	queue<pz> que;
	que.push(p);
	v[p] = true;

	while (!que.empty()) {
		pz g = que.front();
		que.pop();

		bool f = 1;

		for (int i = 0; i < 8; i++) {
			if (g.a[i] != (i + 1)) {
				f = 0;
				break;
			}
		}

		if (f == 1) {
			n = g.t;
			break;
		}

		for (int i = 0; i < 9; i++) {
			if (g.a[i] == 0) {
				if(i % 3 != 0){
					g.t++;
					swap(g.a[i], g.a[i - 1]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i - 1]);
					g.t--;
				}
				if (i % 3 != 2) {
					g.t++;
					swap(g.a[i], g.a[i + 1]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i + 1]);
					g.t--;
				}
				if (i / 3 != 0) {
					g.t++;
					swap(g.a[i], g.a[i - 3]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i - 3]);
					g.t--;
				}
				if (i / 3 != 2) {
					g.t++;
					swap(g.a[i], g.a[i + 3]);
					if (!v[g]) {
						v[g] = true;
						que.push(g);
					}
					swap(g.a[i], g.a[i + 3]);
					g.t--;
				}
			}
		}
	}

	cout << n << endl;

	return 0;
}

```