问题简介：

    所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。

样例：

输入：

1 0 2
3 4 5
6 7 8
0 1 2
3 4 5
6 7 8
输入中前3排表示游戏开始的状态，后3排为结束状态。（题目要求用最少的步数从初始状态变到结束状态）

输出：

1
1 0 2
3 4 5
6 7 8

0 1 2
3 4 5
6 7 8
输出的第一行为最少的步数，接下来每3行一个状态。表示每一步的状态

输入：

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

输出：

0
1 0 2
3 4 5
6 7 8

备注

若输入无解，则输出-1