Mô tả bài toán: Trong Hình 6.10, hình vuông 3x3 bên trái có chứa các thẻ số từ 1 đến 8, và còn lại một ô trống. Thẻ số trong ô cạnh ô trống có thể di chuyển sang vị trí ô trống. Sau một số lần di chuyển, có thể tạo thành trạng thái như trong hình bên phải.

Ghi trạng thái hình bên trái là ‘12345678.’, trạng thái hình bên phải là ‘123.46758’. Đây là cách ghi trạng thái theo thứ tự từ trên xuống dưới, từ trái qua phải, ô trống ký hiệu bằng dấu chấm (‘.’). Cho trạng thái ban đầu và trạng thái đích của ô vuông 3x3, hãy tính số bước di chuyển ít nhất để từ trạng thái ban đầu đến trạng thái đích, nếu không thể đến được thì xuất ra −1.

Input: Dòng đầu tiên là trạng thái ban đầu của ô vuông 3x3, dòng thứ hai là trạng thái đích.

Output: Xuất ra số bước di chuyển ít nhất, nếu không thể đến được thì xuất ra −1.

Input mẫu:

12345678.
123.46758

Output mẫu:

3