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

typedef pair<int,vector<int>> P;

int main(){
	map<vector<int>,int> dist;
	priority_queue<P, vector<P>, greater<P>> q;
	
	vector<int> start(9),end = {1,2,3,4,5,6,7,8,0};
	for(int i=0; i<9; i++) cin>>start[i];
	
	dist[start] = 0;
	q.push(P(0,start));
	
	for(;q.size();){
		int cost = q.top().first;
		vector<int> now = q.top().second;
		q.pop();
		
		if(now==end){
			cout<<cost<<endl;
			break;
		}
		
		vector<vector<int>> next;
		int z = find(now.begin(), now.end(), 0) - now.begin();
		if(z > 2){
			vector<int> nx = now;
			swap(nx[z], nx[z-3]);
			next.push_back(nx);
		}
		if(z < 6){
			vector<int> nx = now;
			swap(nx[z], nx[z+3]);
			next.push_back(nx);
		}
		if(z % 3 > 0){
			vector<int> nx = now;
			swap(nx[z], nx[z-1]);
			next.push_back(nx);
		}
		if(z % 3 < 2){
			vector<int> nx = now;
			swap(nx[z], nx[z+1]);
			next.push_back(nx);
		}
		
		for(auto n : next){
			if(dist.find(n) == dist.end() || 1+cost < dist[n]){
				q.push(P(dist[n]=1+cost, n));
			}
		}
	}
}
### Prompt

Please formulate 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 <bits/stdc++.h>
using namespace std;

typedef pair<int,vector<int>> P;

int main(){
	map<vector<int>,int> dist;
	priority_queue<P, vector<P>, greater<P>> q;
	
	vector<int> start(9),end = {1,2,3,4,5,6,7,8,0};
	for(int i=0; i<9; i++) cin>>start[i];
	
	dist[start] = 0;
	q.push(P(0,start));
	
	for(;q.size();){
		int cost = q.top().first;
		vector<int> now = q.top().second;
		q.pop();
		
		if(now==end){
			cout<<cost<<endl;
			break;
		}
		
		vector<vector<int>> next;
		int z = find(now.begin(), now.end(), 0) - now.begin();
		if(z > 2){
			vector<int> nx = now;
			swap(nx[z], nx[z-3]);
			next.push_back(nx);
		}
		if(z < 6){
			vector<int> nx = now;
			swap(nx[z], nx[z+3]);
			next.push_back(nx);
		}
		if(z % 3 > 0){
			vector<int> nx = now;
			swap(nx[z], nx[z-1]);
			next.push_back(nx);
		}
		if(z % 3 < 2){
			vector<int> nx = now;
			swap(nx[z], nx[z+1]);
			next.push_back(nx);
		}
		
		for(auto n : next){
			if(dist.find(n) == dist.end() || 1+cost < dist[n]){
				q.push(P(dist[n]=1+cost, n));
			}
		}
	}
}
```