import sys



init = ''.join(sys.stdin.read().split())



# Bidirectional search using breadth-first search

def solve(start, goal):

    if start == goal:

        return 0

    generated_state = {start: 0, goal: 1}   # 0: foreward, 1: backward

    step = {start: 0, goal: 0}

    s = 0

    c_d = [(start, 0), (goal, 1)] # configure and direction

    while True:

        q = iter(c_d)

        c_d = []

        s += 1

        for c, d in q:

            i = c.find('0')

            if 0 <= i <= 5:

                t = str.maketrans('0' + c[i+3], c[i+3] + '0')

                t_c = c.translate(t)

                if t_c in generated_state:

                    if generated_state[t_c] != d:

                        return s + step[t_c]

                else:

                    generated_state[t_c] = d

                    step[t_c] = s

                    c_d.append((t_c, d))

            if i >= 3:

                t = str.maketrans('0' + c[i-3], c[i-3] + '0')

                t_c = c.translate(t)

                if t_c in generated_state:

                    if generated_state[t_c] != d:

                        return s + step[t_c]

                else:

                    generated_state[t_c] = d

                    step[t_c] = s

                    c_d.append((t_c, d))

            if i == 0 or i == 1 or i == 3 or i == 4 or i == 6 or i == 7:

                t = str.maketrans('0' + c[i+1], c[i+1] + '0')

                t_c = c.translate(t)

                if t_c in generated_state:

                    if generated_state[t_c] != d:

                        return s + step[t_c]

                else:

                    generated_state[t_c] = d

                    step[t_c] = s

                    c_d.append((t_c, d))

            if i == 1 or i == 2 or i == 4 or i == 5 or i == 7 or i == 8:

                t = str.maketrans('0' + c[i-1], c[i-1] + '0')

                t_c = c.translate(t)

                if t_c in generated_state:

                    if generated_state[t_c] != d:

                        return s + step[t_c]

                else:

                    generated_state[t_c] = d

                    step[t_c] = s

                    c_d.append((t_c, d))



print((solve(init, '123456780')))
adjacent = (

    (1, 3),       # 0

    (0, 2, 4),    # 1

    (1, 5),       # 2

    (0, 4, 6),    # 3

    (1, 3, 5, 7), # 4

    (2, 4, 8),    # 5

    (3, 7),       # 6

    (4, 6, 8),    # 7

    (5, 7)        # 8

)



import collections



GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]



# Bidirectional search using breadth-first search

def solve(start):

    if start == GOAL:

        return 0

    # 0: forward, 1: backward

    generated_state = {tuple(start): 0, tuple(GOAL): 1}

    step = {tuple(start): 0, tuple(GOAL): 0}

    s = 0

    state1 = [(start, 0), (GOAL, 1)]

    while state1:

        state2 = state1[:]

        state1 = []

        s += 1

        for s2, d in state2:

            i = s2.index(0)

            for p in adjacent[i]:

                s1 = s2[:]

                s1[i], s1[p] = s1[p], 0

                key = tuple(s1)

                if key in generated_state:

                    if generated_state[key] != d:

                        return s + step[key]

                    continue

                state1.append((s1, d))

                generated_state[key] = d

                step[key] = s



import sys



start = list(map(int, sys.stdin.read().split()))



print((solve(start)))
import sys

init = "".join(sys.stdin.read().split())
# Bidirectional search using breadth-first search
def solve(start, goal):
    if start == goal:
        return 0
    generated_state = {start: 0, goal: 1}  # 0: foreward, 1: backward
    step = {start: 0, goal: 0}
    s = 0
    c_d = [(start, 0), (goal, 1)]  # configure and direction
    while True:
        q = iter(c_d)
        c_d = []
        s += 1
        for c, d in q:
            i = c.find("0")
            if 0 <= i <= 5:
                t = str.maketrans("0" + c[i + 3], c[i + 3] + "0")
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))
            if i >= 3:
                t = str.maketrans("0" + c[i - 3], c[i - 3] + "0")
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))
            if i == 0 or i == 1 or i == 3 or i == 4 or i == 6 or i == 7:
                t = str.maketrans("0" + c[i + 1], c[i + 1] + "0")
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))
            if i == 1 or i == 2 or i == 4 or i == 5 or i == 7 or i == 8:
                t = str.maketrans("0" + c[i - 1], c[i - 1] + "0")
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))


print((solve(init, "123456780")))

adjacent = (
    (1, 3),  # 0
    (0, 2, 4),  # 1
    (1, 5),  # 2
    (0, 4, 6),  # 3
    (1, 3, 5, 7),  # 4
    (2, 4, 8),  # 5
    (3, 7),  # 6
    (4, 6, 8),  # 7
    (5, 7),  # 8
)
import collections

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]
# Bidirectional search using breadth-first search
def solve(start):
    if start == GOAL:
        return 0
    # 0: forward, 1: backward
    generated_state = {tuple(start): 0, tuple(GOAL): 1}
    step = {tuple(start): 0, tuple(GOAL): 0}
    s = 0
    state1 = [(start, 0), (GOAL, 1)]
    while state1:
        state2 = state1[:]
        state1 = []
        s += 1
        for s2, d in state2:
            i = s2.index(0)
            for p in adjacent[i]:
                s1 = s2[:]
                s1[i], s1[p] = s1[p], 0
                key = tuple(s1)
                if key in generated_state:
                    if generated_state[key] != d:
                        return s + step[key]
                    continue
                state1.append((s1, d))
                generated_state[key] = d
                step[key] = s


import sys

start = list(map(int, sys.stdin.read().split()))
print((solve(start)))

+adjacent = ( +    (1, 3),  # 0 +    (0, 2, 4),  # 1 +    (1, 5),  # 2 +    (0, 4, 6),  # 3 +    (1, 3, 5, 7),  # 4 +    (2, 4, 8),  # 5 +    (3, 7),  # 6 +    (4, 6, 8),  # 7 +    (5, 7),  # 8 +) +import collections + +GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0] +# Bidirectional search using breadth-first search +def solve(start): +    if start == GOAL: +        return 0 +    # 0: forward, 1: backward +    generated_state = {tuple(start): 0, tuple(GOAL): 1} +    step = {tuple(start): 0, tuple(GOAL): 0} +    s = 0 +    state1 = [(start, 0), (GOAL, 1)] +    while state1: +        state2 = state1[:] +        state1 = [] +        s += 1 +        for s2, d in state2: +            i = s2.index(0) +            for p in adjacent[i]: +                s1 = s2[:] +                s1[i], s1[p] = s1[p], 0 +                key = tuple(s1) +                if key in generated_state: +                    if generated_state[key] != d: +                        return s + step[key] +                    continue +                state1.append((s1, d)) +                generated_state[key] = d +                step[key] = s + + -init = "".join(sys.stdin.read().split()) -# Bidirectional search using breadth-first search -def solve(start, goal): -    if start == goal: -        return 0 -    generated_state = {start: 0, goal: 1}  # 0: foreward, 1: backward -    step = {start: 0, goal: 0} -    s = 0 -    c_d = [(start, 0), (goal, 1)]  # configure and direction -    while True: -        q = iter(c_d) -        c_d = [] -        s += 1 -        for c, d in q: -            i = c.find("0") -            if 0 <= i <= 5: -                t = str.maketrans("0" + c[i + 3], c[i + 3] + "0") -                t_c = c.translate(t) -                if t_c in generated_state: -                    if generated_state[t_c] != d: -                        return s + step[t_c] -                else: -                    generated_state[t_c] = d -                    step[t_c] = s -                    c_d.append((t_c, d)) -            if i >= 3: -                t = str.maketrans("0" + c[i - 3], c[i - 3] + "0") -                t_c = c.translate(t) -                if t_c in generated_state: -                    if generated_state[t_c] != d: -                        return s + step[t_c] -                else: -                    generated_state[t_c] = d -                    step[t_c] = s -                    c_d.append((t_c, d)) -            if i == 0 or i == 1 or i == 3 or i == 4 or i == 6 or i == 7: -                t = str.maketrans("0" + c[i + 1], c[i + 1] + "0") -                t_c = c.translate(t) -                if t_c in generated_state: -                    if generated_state[t_c] != d: -                        return s + step[t_c] -                else: -                    generated_state[t_c] = d -                    step[t_c] = s -                    c_d.append((t_c, d)) -            if i == 1 or i == 2 or i == 4 or i == 5 or i == 7 or i == 8: -                t = str.maketrans("0" + c[i - 1], c[i - 1] + "0") -                t_c = c.translate(t) -                if t_c in generated_state: -                    if generated_state[t_c] != d: -                        return s + step[t_c] -                else: -                    generated_state[t_c] = d -                    step[t_c] = s -                    c_d.append((t_c, d)) - - -print((solve(init, "123456780"))) +start = list(map(int, sys.stdin.read().split())) +print((solve(start)))