import sys



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



generated_state = {init: 0}



def bfs(root):

    s = 0

    configure = [root]

    while '123456780' not in configure:

        q = iter(configure)

        configure = []

        s += 1

        for c 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 not in generated_state:

                    generated_state[t_c] = s

                    configure.append(t_c)

            if i >= 3:

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

                t_c = c.translate(t)

                if t_c not in generated_state:

                    generated_state[t_c] = s

                    configure.append(t_c)

            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 not in generated_state:

                    generated_state[t_c] = s

                    configure.append(t_c)

            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 not in generated_state:

                    generated_state[t_c] = s

                    configure.append(t_c)

            if '123456780' in generated_state:

                break

    print(s)



bfs(init)
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')))
import sys

init = "".join(sys.stdin.read().split())
generated_state = {init: 0}


def bfs(root):
    s = 0
    configure = [root]
    while "123456780" not in configure:
        q = iter(configure)
        configure = []
        s += 1
        for c 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 not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            if i >= 3:
                t = str.maketrans("0" + c[i - 3], c[i - 3] + "0")
                t_c = c.translate(t)
                if t_c not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            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 not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            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 not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            if "123456780" in generated_state:
                break
    print(s)


bfs(init)

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")))

-generated_state = {init: 0} - - -def bfs(root): +# 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} -    configure = [root] -    while "123456780" not in configure: -        q = iter(configure) -        configure = [] +    c_d = [(start, 0), (goal, 1)]  # configure and direction +    while True: +        q = iter(c_d) +        c_d = [] -        for c in q: +        for c, d in q: -                if t_c not in generated_state: -                    generated_state[t_c] = s -                    configure.append(t_c) +                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 t_c not in generated_state: -                    generated_state[t_c] = s -                    configure.append(t_c) +                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 t_c not in generated_state: -                    generated_state[t_c] = s -                    configure.append(t_c) +                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 t_c not in generated_state: -                    generated_state[t_c] = s -                    configure.append(t_c) -            if "123456780" in generated_state: -                break -    print(s) +                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)) -bfs(init) +print((solve(init, "123456780")))