时间限制：1秒　　内存限制：256M

---

【题目描述】

　　编号为 1..8 的 8 个正方形滑块被摆成 3 行 3 列（有一个格子留空），如图所示。每次可以把与空格相邻的滑块（有公共边才算相邻）移到空格中，而它原来的位置就成为一个新空格。给定初始局面和目标局面（用 0 表示空格），你的任务是计算出最少的移动步骤。如果无法到达目标局面，则输出 -1。

【输入格式】

　　第一行：初始局面，数字之间用一个空格分开；
　　第二行：目标局面，数字之间用一个空格分开。

【输出格式】

　　一个整数，表示最少的变换步骤，如果无法达到目标局面，则输出 -1。

【输入输出样例】

　Input

2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2

　Output

31

【来源】

　　Mr.he