题目描述

一个 $3\times 3$ 的拼盘里放着 $8$ 个写着数字 $1\sim 8$ 的方块，还剩 $1$ 个空格（用 0 表示）。空格与上下左右相邻的方块可以互换位置，记作一次滑动。

目标状态是：

1 2 3
4 5 6
7 8 0

给定初始状态，求把它还原成目标状态所需的最少滑动次数。如果无论怎么滑都无法还原，输出 $-1$。

输入格式

输入共 $3$ 行，每行 $3$ 个整数，按从上到下、从左到右的顺序给出初始状态，$0$ 表示空格。

输出格式

一行一个整数，表示最少滑动次数，或 $-1$。

输入输出样例 #1

输入 #1

1 2 3
4 0 6
7 5 8

输出 #1

2

说明

数据范围

• 对于 $100\%$ 的数据，输入保证是一个合法的状态：$0\sim 8$ 每个数恰好出现一次。