#include <iostream>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N = 3;
const int N2 = 9;
const int x[4] = {0, 0, 1, -1};
const int y[4] = {-1, 1, 0, 0};
const char ch[4] = {'l', 'r', 'd', 'u'};

class node{
public:
	int f[N2];
	int space;
	string str;
	bool operator< (const node& n) const
	{
		for (int i = 0; i < N2; ++i)
		{
			if (n.f[i] == f[i])
				continue;
			return f[i] > n.f[i];
		}
		return false;
	} 
};

bool Is_Return(const node& n)
{
	for (int i = 0; i < N2; ++i)
	{
		if (n.f[i] != i + 1)
			return false;
	}
	return true;
}

string bfs(node& n)
{
	queue<node> Q;
	map<node, bool> ans;
	Q.push(n);
	ans[n] = true;
	while (!Q.empty())
	{
		node u = Q.front();
		Q.pop();
		if (Is_Return(u))
			return u.str;
		int tx = u.space / N;
		int ty = u.space % N;
		for (int i = 0; i < 4; ++i)
		{
			int sx = tx + x[i];
			int sy = ty + y[i];
			if (sx < 0 || sy < 0 || sx >= N || sy >= N)
				continue;
			node v = u;
			swap(v.f[v.space], v.f[sx * N + sy]);
			v.space = sx * N + sy;
			if (!ans[v])
			{
				ans[v] = true;
				v.str += ch[i];
				Q.push(v);
			}
		}
	}
	return "unsolvable";
}

int main()
{
	node n;
	for (int i = 0; i < N2; ++i)
	{  
		cin >> n.f[i];
		if (n.f[i] == 0)
		{
			n.space = i;
			n.f[i] = N2;
		}
	}
	string s = bfs(n);
	cout << s.length() << endl;
	return 0;
}

### Prompt

Your challenge is to write 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 <iostream>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N = 3;
const int N2 = 9;
const int x[4] = {0, 0, 1, -1};
const int y[4] = {-1, 1, 0, 0};
const char ch[4] = {'l', 'r', 'd', 'u'};

class node{
public:
	int f[N2];
	int space;
	string str;
	bool operator< (const node& n) const
	{
		for (int i = 0; i < N2; ++i)
		{
			if (n.f[i] == f[i])
				continue;
			return f[i] > n.f[i];
		}
		return false;
	} 
};

bool Is_Return(const node& n)
{
	for (int i = 0; i < N2; ++i)
	{
		if (n.f[i] != i + 1)
			return false;
	}
	return true;
}

string bfs(node& n)
{
	queue<node> Q;
	map<node, bool> ans;
	Q.push(n);
	ans[n] = true;
	while (!Q.empty())
	{
		node u = Q.front();
		Q.pop();
		if (Is_Return(u))
			return u.str;
		int tx = u.space / N;
		int ty = u.space % N;
		for (int i = 0; i < 4; ++i)
		{
			int sx = tx + x[i];
			int sy = ty + y[i];
			if (sx < 0 || sy < 0 || sx >= N || sy >= N)
				continue;
			node v = u;
			swap(v.f[v.space], v.f[sx * N + sy]);
			v.space = sx * N + sy;
			if (!ans[v])
			{
				ans[v] = true;
				v.str += ch[i];
				Q.push(v);
			}
		}
	}
	return "unsolvable";
}

int main()
{
	node n;
	for (int i = 0; i < N2; ++i)
	{  
		cin >> n.f[i];
		if (n.f[i] == 0)
		{
			n.space = i;
			n.f[i] = N2;
		}
	}
	string s = bfs(n);
	cout << s.length() << endl;
	return 0;
}

```