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";
}