#0J/QsNGA0YXQvtC80LXQvdC60L4=
from collections import deque
 
 
HORSES_MOVES = [
    (2, 1), (2, -1), (-2, 1), (-2, -1),
    (1, 2), (1, -2), (-1, 2), (-1, -2)
]
 
 
def under_attack_by_queen(x, y, qx, qy):
    return (
        x == qx or
        y == qy or
        abs(x - qx) == abs(y - qy)
    )
 
 
def bfs(N, horse, queen, target):
    kx, ky = horse
    qx, qy = queen
    tx, ty = target
 
 
    visited = [[[False, False] for _ in range(N)] for _ in range(N)]
    queue = deque()
 
 
    queue.append((kx, ky, 1, 0))
    visited[kx][ky][1] = True
 
    while queue:
        x, y, alive, dist = queue.popleft()
 
        if (x, y) == (tx, ty):
            return dist
 
        for dx, dy in HORSES_MOVES:
            nx, ny = x + dx, y + dy
 
            if not (0 <= nx < N and 0 <= ny < N):
                continue
 
            next_alive = alive
 
            if alive:
 
                if (nx, ny) == (qx, qy):
                    next_alive = 0
                else:
 
                    if under_attack_by_queen(nx, ny, qx, qy):
                        continue
 
 
            if not visited[nx][ny][next_alive]:
                visited[nx][ny][next_alive] = True
                queue.append((nx, ny, next_alive, dist + 1))
 
    return -1
 
 
 
if __name__ == "__main__":
    N = 8
    horse = (2, 1)
    queen = (3, 3)
    target = (7, 7)
 
    result = bfs(N, horse, queen, target)
    print("Мінімальна кількість ходів:", result)
 

IzBKL1FzTkdBMFlYUXZ0QzgwTFhRdmRDNjBMND0KZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKCgpIT1JTRVNfTU9WRVMgPSBbCiAgICAoMiwgMSksICgyLCAtMSksICgtMiwgMSksICgtMiwgLTEpLAogICAgKDEsIDIpLCAoMSwgLTIpLCAoLTEsIDIpLCAoLTEsIC0yKQpdCgoKZGVmIHVuZGVyX2F0dGFja19ieV9xdWVlbih4LCB5LCBxeCwgcXkpOgogICAgcmV0dXJuICgKICAgICAgICB4ID09IHF4IG9yCiAgICAgICAgeSA9PSBxeSBvcgogICAgICAgIGFicyh4IC0gcXgpID09IGFicyh5IC0gcXkpCiAgICApCgoKZGVmIGJmcyhOLCBob3JzZSwgcXVlZW4sIHRhcmdldCk6CiAgICBreCwga3kgPSBob3JzZQogICAgcXgsIHF5ID0gcXVlZW4KICAgIHR4LCB0eSA9IHRhcmdldAoKCiAgICB2aXNpdGVkID0gW1tbRmFsc2UsIEZhbHNlXSBmb3IgXyBpbiByYW5nZShOKV0gZm9yIF8gaW4gcmFuZ2UoTildCiAgICBxdWV1ZSA9IGRlcXVlKCkKCgogICAgcXVldWUuYXBwZW5kKChreCwga3ksIDEsIDApKQogICAgdmlzaXRlZFtreF1ba3ldWzFdID0gVHJ1ZQoKICAgIHdoaWxlIHF1ZXVlOgogICAgICAgIHgsIHksIGFsaXZlLCBkaXN0ID0gcXVldWUucG9wbGVmdCgpCgogICAgICAgIGlmICh4LCB5KSA9PSAodHgsIHR5KToKICAgICAgICAgICAgcmV0dXJuIGRpc3QKCiAgICAgICAgZm9yIGR4LCBkeSBpbiBIT1JTRVNfTU9WRVM6CiAgICAgICAgICAgIG54LCBueSA9IHggKyBkeCwgeSArIGR5CgogICAgICAgICAgICBpZiBub3QgKDAgPD0gbnggPCBOIGFuZCAwIDw9IG55IDwgTik6CiAgICAgICAgICAgICAgICBjb250aW51ZQoKICAgICAgICAgICAgbmV4dF9hbGl2ZSA9IGFsaXZlCgogICAgICAgICAgICBpZiBhbGl2ZToKCiAgICAgICAgICAgICAgICBpZiAobngsIG55KSA9PSAocXgsIHF5KToKICAgICAgICAgICAgICAgICAgICBuZXh0X2FsaXZlID0gMAogICAgICAgICAgICAgICAgZWxzZToKCiAgICAgICAgICAgICAgICAgICAgaWYgdW5kZXJfYXR0YWNrX2J5X3F1ZWVuKG54LCBueSwgcXgsIHF5KToKICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWUKCgogICAgICAgICAgICBpZiBub3QgdmlzaXRlZFtueF1bbnldW25leHRfYWxpdmVdOgogICAgICAgICAgICAgICAgdmlzaXRlZFtueF1bbnldW25leHRfYWxpdmVdID0gVHJ1ZQogICAgICAgICAgICAgICAgcXVldWUuYXBwZW5kKChueCwgbnksIG5leHRfYWxpdmUsIGRpc3QgKyAxKSkKCiAgICByZXR1cm4gLTEKCgoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIE4gPSA4CiAgICBob3JzZSA9ICgyLCAxKQogICAgcXVlZW4gPSAoMywgMykKICAgIHRhcmdldCA9ICg3LCA3KQoKICAgIHJlc3VsdCA9IGJmcyhOLCBob3JzZSwgcXVlZW4sIHRhcmdldCkKICAgIHByaW50KCLQnNGW0L3RltC80LDQu9GM0L3QsCDQutGW0LvRjNC60ZbRgdGC0Ywg0YXQvtC00ZbQsjoiLCByZXN1bHQpCg==