题目背景

抽屉里翻出一只旧式的九宫滑块玩具：$3 \times 3$ 的盘面里嵌着编号 $1 \sim 8$ 的方片，还剩一个空格。每次只能把空格上下左右相邻的方片滑进空格。你把它随手打乱之后，想让方片重新按编号顺序排好，空格落在右下角。

题目描述

给定一个 $3 \times 3$ 的盘面，其中 $0$ 表示空格，其余八个格子为 $1 \sim 8$ 各一个。一次操作可以把与空格相邻的方片滑入空格（等价于把空格与该方片交换位置）。求把盘面变回

1 2 3
4 5 6
7 8 0

所需的最少操作次数；若无论如何都还原不了，输出 $-1$。

输入格式

三行，每行三个整数，表示初始盘面。

输出格式

一行一个整数，表示最少操作次数；若无法还原则输出 -1。

输入输出样例 #1

输入 #1

1 2 3
4 5 6
7 8 0

输出 #1

0

输入输出样例 #2

输入 #2

1 2 3
4 5 6
7 0 8

输出 #2

1

输入输出样例 #3

输入 #3

2 1 3
4 5 6
7 8 0

输出 #3

-1

说明

样例解释

样例 1：盘面已经归位，不需要任何操作。

样例 2：把 $8$ 号方片滑入空格即可归位，共 $1$ 次操作。

样例 3：$1$ 号与 $2$ 号方片的位置互换了。在 $3 \times 3$ 的盘面上，只有方片排列为偶排列的盘面才能还原，而该盘面除去空格后是奇排列，故输出 $-1$。

数据范围

• 对于 $30\%$ 的数据，最少操作次数不超过 $4$（无法还原的盘面不计入该档）；
• 对于 $60\%$ 的数据，最少操作次数不超过 $20$（无法还原的盘面不计入该档）；
• 对于 $100\%$ 的数据，输入的盘面是 $0 \sim 8$ 的一个排列。