时间限制:1000ms  空间限制:256MB

题目描述

八数码问题：给定一个初始状态

1 2 3
4 5 6
7 8 0

每次可以把 $0$ 和与它相邻的数字交换，问最少需要多少步，可以转换到目标状态。

输入格式

三行三个整数，用空格隔开，分别表示了目标状态的三行。

输出格式

假如无法从初始状态到目标状态，输出一行"Impossible"(不含引号)，否则输出最少需要的步数。

样例

输入#1

1 2 3
4 5 6
0 7 8

输出#1

2

数据范围/约定

无