import queue

moves = {
    0: {1, 3},
    1: {0, 2, 4},
    2: {1, 5},
    3: {0, 4},
    4: {1, 3, 5},
    5: {2, 4}
}

class Solution:
    def slidingPuzzle(self, board):
        """
        :type board: List[List[int]]
        :rtype: int
        """
        result = 0

        _ = board[0] + board[1]
        s = ''.join(str(x) for x in _)

        q = queue.Queue()
        q.put(s)
        q1 = queue.Queue()

        m = set()

        while not q.empty():
            x = q.get()
            if x == '123450':
                return result
            oz = x.find('0')
            for nz in moves[oz]:
                ns = ''
                for j in range(0, 6):
                    if j == oz:
                        ns += x[nz]
                    elif j == nz:
                        ns += x[oz]
                    else:
                        ns += x[j]
                if ns not in m:
                    m.add(ns)
                    q1.put(ns)

            if q.empty():
                result += 1
                q1, q = q, q1

        return -1