import heapq

def solve():
    file = "input.txt"
    grid_size = 71
    start = (0, 0)
    end = (grid_size - 1, grid_size - 1)

    with open(file) as f:
        bytes = []
        for line in f:
            x, y = map(int, line.strip().split(','))
            bytes.append((x, y))

    def is_valid(x, y):
        return 0 <= x < grid_size and 0 <= y < grid_size

    def shortest_path(corrupted):
        q = [(0, start)]
        visited = set()
        while q:
            dist, (x, y) = heapq.heappop(q)
            if (x, y) == end:
                return dist
            if (x, y) in visited or (x, y) in corrupted:
                continue
            visited.add((x, y))
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if is_valid(nx, ny):
                    heapq.heappush(q, (dist + 1, (nx, ny)))
        return -1

    # Part 1
    corrupted1 = set(bytes[:1024])
    part1_result = shortest_path(corrupted1)
    print(part1_result)

    # Part 2
    corrupted2 = set()
    for i in range(len(bytes)):
        corrupted2.add(bytes[i])
        if shortest_path(corrupted2) == -1:
            print(f"{bytes[i][0]},{bytes[i][1]}")
            break

solve()