题目描述

FJ 为了让奶牛在空闲的时候不至于太过无聊，于是给他们发放了一个滑动拼板，拼板是一个 \(3\) 行 \(3\) 列的格子，有 \(8\) 个格子各有一块可以滑动的小方块，有一个格子是空的，和空格子相邻的方块就可以滑动到这个空格子里面，同时自己原来的位置就变成了空格子，如下图所的开始状态(用点号“ \(.\) ”表示空格子）：

123
456
78.

经过多次移动后，可以形成如下所示的结束状态

123
.46
758

FJ 把第一个状态记为：\(\text{12345678}\).

把第 \(2\) 个状态记为：\(\text{123.46758}\)

现在给定一个初始状态和结束状态，请你帮忙计算最少需要经过多少步移动才能到达，如果无法到达，输出 \(-1\)。

格式

输入格式

输入第 \(1\) 行包含 \(1\) 到 \(8\) 这 \(8\) 个数字和一个点号“ \(.\) ”的字符串，表示开始状态
输入第 \(2\) 行包含 \(1\) 到 \(8\) 这 \(8\) 个数字和一个点号“ \(.\) ”的字符串，表示结束状态

输出格式

输出一行一个整数，表示从开始状态到结束状态所需要的最小步数，若无法到达输出 \(-1\)。

样例1

样例输入1

12345678.
123.46758

样例输出1

3

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T4\)