from collections import deque
import copy

def read_input(file_path):
    coordinates = []
    with open(file_path, 'r') as f:
        for line in f:
            x, y = map(int, line.strip().split(','))
            coordinates.append((x, y))
    return coordinates

def create_grid(size):
    return [[False for _ in range(size)] for _ in range(size)]

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

def get_neighbors(x, y, grid):
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    size = len(grid)
    neighbors = []
    for dx, dy in directions:
        new_x, new_y = x + dx, y + dy
        if is_valid(new_x, new_y, size) and not grid[new_y][new_x]:
            neighbors.append((new_x, new_y))
    return neighbors

def shortest_path(grid, start, end):
    if grid[start[1]][start[0]] or grid[end[1]][end[0]]:
        return float('inf')
    
    queue = deque([(start[0], start[1], 0)])
    visited = {start}
    
    while queue:
        x, y, dist = queue.popleft()
        if (x, y) == end:
            return dist
            
        for next_x, next_y in get_neighbors(x, y, grid):
            if (next_x, next_y) not in visited:
                visited.add((next_x, next_y))
                queue.append((next_x, next_y, dist + 1))
    
    return float('inf')

def path_exists(grid, start, end):
    if grid[start[1]][start[0]] or grid[end[1]][end[0]]:
        return False
    
    queue = deque([start])
    visited = {start}
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == end:
            return True
            
        for next_x, next_y in get_neighbors(x, y, grid):
            if (next_x, next_y) not in visited:
                visited.add((next_x, next_y))
                queue.append((next_x, next_y))
    
    return False

def solve_part1(coordinates, size=71):
    grid = create_grid(size)
    for i in range(1024):
        if i >= len(coordinates):
            break
        x, y = coordinates[i]
        grid[y][x] = True
    
    result = shortest_path(grid, (0, 0), (size-1, size-1))
    return str(result)

def solve_part2(coordinates, size=71):
    grid = create_grid(size)
    for i, (x, y) in enumerate(coordinates):
        grid[y][x] = True
        if not path_exists(grid, (0, 0), (size-1, size-1)):
            return f"{x},{y}"
    return "No solution found"

coordinates = read_input("./input.txt")
print(solve_part1(coordinates))
print(solve_part2(coordinates))