Sliding Puzzle

A sliding puzzle consists of a 2 x 3 board with tiles numbered 1 to 5 and one empty space represented by 0. The board is represented as a 2 x 3 matrix. For example:

The configuration above is represented by [[4, 1, 3], [2, 0, 5]].

Each move swaps the empty space with an adjacent tile (horizontally or vertically). The goal is to reach the solved state [[1, 2, 3], [4, 5, 0]]:

Given an initial board configuration, find the minimum number of moves to reach the solved state, or return -1 if impossible.

Input

init_pos: an integer matrix representing the initial position of the puzzle.

Output

The number of steps required to solve this puzzle, or -1 if the puzzle is impossible to solve.

Examples

Example 1:

Input:

init_pos = [[4, 1, 3], [2, 0, 5]]

Output: 5

Explanation:

Constraints

The input must be a 2 x 3 integer matrix containing exactly one of each from 0 to 5