#0J/QsNGA0YXQvtC80LXQvdC60L4g
#%%
from collections import deque
 
def rook_distance(a, b):
    (x1, y1) = a
    (x2, y2) = b
    if a == b:
        return 0
    if x1 == x2 or y1 == y2:
        return 1
    return 2  
 
 
def min_moves(m, rook_pos, black_pieces):
 
    n = len(black_pieces)
    dist = [[0] * n for _ in range(n)]
    rook_to_piece = [0] * n
 
    for i in range(n):
        rook_to_piece[i] = rook_distance(rook_pos, black_pieces[i])
 
    for i in range(n):
        for j in range(n):
            dist[i][j] = rook_distance(black_pieces[i], black_pieces[j])
 
    INF = 10**9
    dp = [[INF] * n for _ in range(1 << n)]
 
    queue = deque()
 
 
    for i in range(n):
        mask = 1 << i
        dp[mask][i] = rook_to_piece[i]
        queue.append((mask, i))
 
 
    while queue:
        mask, last = queue.popleft()
        current_cost = dp[mask][last]
 
        for nxt in range(n):
            if mask & (1 << nxt):
                continue
            new_mask = mask | (1 << nxt)
            new_cost = current_cost + dist[last][nxt]
 
            if new_cost < dp[new_mask][nxt]:
                dp[new_mask][nxt] = new_cost
                queue.append((new_mask, nxt))
 
    full_mask = (1 << n) - 1
    return min(dp[full_mask]) if n > 0 else 0
if __name__ == "__main__":
    m = 20
    rook_pos = (1, 1)
    black_pieces = [(13, 5), (3, 7), (6, 17), (7, 20)]
 
    print("Мінімальна кількість ходів:", min_moves(m, rook_pos, black_pieces))
 

IzBKL1FzTkdBMFlYUXZ0QzgwTFhRdmRDNjBMNGcKIyUlCmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IGRlcXVlCgpkZWYgcm9va19kaXN0YW5jZShhLCBiKToKICAgICh4MSwgeTEpID0gYQogICAgKHgyLCB5MikgPSBiCiAgICBpZiBhID09IGI6CiAgICAgICAgcmV0dXJuIDAKICAgIGlmIHgxID09IHgyIG9yIHkxID09IHkyOgogICAgICAgIHJldHVybiAxCiAgICByZXR1cm4gMiAgCgoKZGVmIG1pbl9tb3ZlcyhtLCByb29rX3BvcywgYmxhY2tfcGllY2VzKToKCiAgICBuID0gbGVuKGJsYWNrX3BpZWNlcykKICAgIGRpc3QgPSBbWzBdICogbiBmb3IgXyBpbiByYW5nZShuKV0KICAgIHJvb2tfdG9fcGllY2UgPSBbMF0gKiBuCgogICAgZm9yIGkgaW4gcmFuZ2Uobik6CiAgICAgICAgcm9va190b19waWVjZVtpXSA9IHJvb2tfZGlzdGFuY2Uocm9va19wb3MsIGJsYWNrX3BpZWNlc1tpXSkKCiAgICBmb3IgaSBpbiByYW5nZShuKToKICAgICAgICBmb3IgaiBpbiByYW5nZShuKToKICAgICAgICAgICAgZGlzdFtpXVtqXSA9IHJvb2tfZGlzdGFuY2UoYmxhY2tfcGllY2VzW2ldLCBibGFja19waWVjZXNbal0pCgogICAgSU5GID0gMTAqKjkKICAgIGRwID0gW1tJTkZdICogbiBmb3IgXyBpbiByYW5nZSgxIDw8IG4pXQoKICAgIHF1ZXVlID0gZGVxdWUoKQoKICAgIAogICAgZm9yIGkgaW4gcmFuZ2Uobik6CiAgICAgICAgbWFzayA9IDEgPDwgaQogICAgICAgIGRwW21hc2tdW2ldID0gcm9va190b19waWVjZVtpXQogICAgICAgIHF1ZXVlLmFwcGVuZCgobWFzaywgaSkpCgogICAgCiAgICB3aGlsZSBxdWV1ZToKICAgICAgICBtYXNrLCBsYXN0ID0gcXVldWUucG9wbGVmdCgpCiAgICAgICAgY3VycmVudF9jb3N0ID0gZHBbbWFza11bbGFzdF0KCiAgICAgICAgZm9yIG54dCBpbiByYW5nZShuKToKICAgICAgICAgICAgaWYgbWFzayAmICgxIDw8IG54dCk6CiAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICBuZXdfbWFzayA9IG1hc2sgfCAoMSA8PCBueHQpCiAgICAgICAgICAgIG5ld19jb3N0ID0gY3VycmVudF9jb3N0ICsgZGlzdFtsYXN0XVtueHRdCgogICAgICAgICAgICBpZiBuZXdfY29zdCA8IGRwW25ld19tYXNrXVtueHRdOgogICAgICAgICAgICAgICAgZHBbbmV3X21hc2tdW254dF0gPSBuZXdfY29zdAogICAgICAgICAgICAgICAgcXVldWUuYXBwZW5kKChuZXdfbWFzaywgbnh0KSkKCiAgICBmdWxsX21hc2sgPSAoMSA8PCBuKSAtIDEKICAgIHJldHVybiBtaW4oZHBbZnVsbF9tYXNrXSkgaWYgbiA+IDAgZWxzZSAwCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBtID0gMjAKICAgIHJvb2tfcG9zID0gKDEsIDEpCiAgICBibGFja19waWVjZXMgPSBbKDEzLCA1KSwgKDMsIDcpLCAoNiwgMTcpLCAoNywgMjApXQoKICAgIHByaW50KCLQnNGW0L3RltC80LDQu9GM0L3QsCDQutGW0LvRjNC60ZbRgdGC0Ywg0YXQvtC00ZbQsjoiLCBtaW5fbW92ZXMobSwgcm9va19wb3MsIGJsYWNrX3BpZWNlcykpCg==