sub isValid {
    my ($n, $new_x, $new_y, $visited) = @_;
    return 1 if ($new_x >= 0 && $new_x < $n && $new_y >= 0 && $new_y < $n && !$visited->{"$new_x, $new_y"});
}

sub printShortestPath {
    my ($n, $start_x, $start_y, $end_x, $end_y) = @_;

    my %positions = (
        "UL" => [-2, -1],
        "UR" => [-2,  1],
        "R"  => [ 0,  2],
        "LR" => [ 2,  1],
        "LL" => [ 2, -1],
        "L"  => [ 0, -2]
    );
    my @directions = qw(UL UR R LR LL L);

    my $queue = [[$start_x, $start_y, []]];
    my %visited;
    $visited{"$start_x, $start_y"} = 1;

    while (@$queue) {
        my ($curr_x, $curr_y, $path) = @{shift(@$queue)};

        if ($curr_x == $end_x && $curr_y == $end_y) {
            print scalar(@$path) . "\n";
            print join(" ", @$path) . "\n";
            return;
        }

        foreach my $direction (@directions) {
            my ($dr, $dc) = @{$positions{$direction}};
            my ($new_x, $new_y) = ($curr_x + $dr, $curr_y + $dc);

            if (isValid($n, $new_x, $new_y, \%visited)) {
                $visited{"$new_x, $new_y"} = 1;
                push(@$queue, [$new_x, $new_y, [@$path, $direction]]);
            }
        }
    }

    print "Impossible\n";
}

def is_valid(i, j, n):
    if i >= 0 and i < n and j >= 0 and j < n:
        return True
        
    return False
    
    
def get_neighbours(loc, n):
    i, j = loc[0], loc[1]
    name = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
    dr = [-2, -2, 0, 2, 2, 0]
    cr = [-1, 1, 2, 1, -1, -2]
    res = []
    
    for d in range(6):
        if is_valid(i+dr[d], j+cr[d], n):
            res.append([(i+dr[d], j+cr[d]), name[d]])
    
    return res
    
def printShortestPath(n, i_start, j_start, i_end, j_end):
    # Print the distance along with the sequence of moves.
    parent_dict = {(i_start, j_start): None}
    front_tier = [(i_start, j_start)]
    _next = []
    lvl = 0
    tgt = (i_end, j_end)
    
    def print_res(v):
        res = []
        cur = v
        while True:
            parent = parent_dict[cur]
            
            if parent is None:
                for i in range(len(res)-1, -1, -1):
                    print(res[i], end=' ')
                return
            
            res.append(parent[1])
            cur = parent[0]
            
    while front_tier:
        for v in front_tier:
            if v == tgt:
                print(lvl)
                print_res(v)
                return
                
            neighbours = get_neighbours(v, n)
            for neighbour in neighbours:
                if neighbour[0] not in parent_dict:
                    _next.append(neighbour[0])
                    parent_dict[neighbour[0]] = [v, neighbour[1]]
        
        lvl += 1
        front_tier = _next
        _next = []
    
    print('Impossible')

void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) {
    std::vector<std::tuple<int, int, std::string>> direct = {{-2, -1, "UL"}, {-2, 1, "UR"}, {0, 2, "R"},{2, 1, "LR"},{2, -1, "LL"},{0, -2, "L"}};
    // Print the distance along with the sequence of moves.
   queue<std::tuple<int, int, std::string>> pq;
    vector<vector<bool>> vis(n, vector<bool>(n, false));
    vis[i_start][j_start] = true;
    // add start point
    int steps = 0;
    pq.emplace(i_start, j_start, string(""));
    int step = 0;
    while(!pq.empty()) {
        int size = pq.size();
        steps++;
        while (size--) {
           auto [r, c, path] = pq.front();
            pq.pop();
            // reach target node
            if (r == i_end && c == j_end) {
                cout << steps-1 << endl; 
                cout << path << endl;
                return;
            }
            for (const auto& [nb_r, nb_c, name]: direct) {
                int new_r = r + nb_r;
                int new_c = c + nb_c;
                // validate node
                if (new_r >= 0 && new_r <n && new_c>=0 && new_c <n && !vis[new_r][new_c]){
                    vis[new_r][new_c] = true;
                    pq.emplace(new_r, new_c, path + name + " ");
                    }
                }
            }
        } 
    // not found any path
    cout << "Impossible" << endl;
}

class Node:
    def __init__(self, x, y):
        self.state = (x, y)
        self.parent: Node = None
        self.action: str


def find_path(node):
    path = []
    while node.parent is not None:
        path.append(node.action)
        node = node.parent
    return path[::-1]  # Reverse the path to get the correct order


def actions(current_node, n):
    current_r, current_c = current_node.state

    children = []

    # a = [UL, UR, R, LR, LL, L]
    dr = [-2, -2, 0, 2, 2, 0]
    dc = [-1, 1, 2, 1, -1, -2]

    for i in range(0, 6):

        possible_r = current_r + dr[i]
        possible_c = current_c + dc[i]

        # Check it is not out of bounds.
        if possible_r < 0 or possible_c < 0:
            continue
        if possible_r > n - 1 or possible_c > n - 1:
            continue

        child = Node(possible_r, possible_c)
        child.parent = current_node

        if i == 0:
            child.action = "UL"
        elif i == 1:
            child.action = "UR"
        elif i == 2:
            child.action = "R"
        elif i == 3:
            child.action = "LR"
        elif i == 4:
            child.action = "LL"
        elif i == 5:
            child.action = "L"

        children.append(child)
    return children


def printShortestPath(n, i_start, j_start, i_end, j_end):
    # start_node = Node(i_start, j_start)
    start_node = Node(i_start, j_start)
    goal_node = Node(i_end, j_end)

    visited = set()
    queue = [start_node]
    while queue:
        current_node = queue.pop(0)

        if current_node.state == goal_node.state:
            path = find_path(current_node)
            print(len(path))
            print(' '.join(path))
            return

        if current_node.state not in visited:
            visited.add(current_node.state)

        children = actions(current_node, n)

        for child in children:
            if child.state not in visited and child not in queue:
                visited.add(child.state)  # Nodes are added to the visited set as soon as they are added to the queue,
                # ensuring they are not re-added.
                queue.append(child)

    print("Impossible")