sub is-perfect-square ( UInt $n --> Bool ) {
    return $n.sqrt.round.² == $n;
}

sub task2_slow ( @ns --> Seq ) {
    sub all-pairs-sum-to-perfect-squares ( @p --> Bool ) {
        return @p.rotor(2 => -1).map( *.sum.&is-perfect-square ).all.so;
    }
    return @ns.permutations.grep(&all-pairs-sum-to-perfect-squares).sort.squish(:with(&[eqv]));
}

sub task2 ( @ns --> Seq ) {
    my %square_pairs = @ns.map: -> $a {
        $a => @ns.grep( -> $b { is-perfect-square( $a + $b ) } ).Set;
    }

    my BagHash $n_count = @ns.BagHash;

    sub recursing ( UInt $head ) {
        return $head if not $n_count;

        return gather for %square_pairs{$head}{ $n_count.keys }:k -> UInt $c {
            $n_count{$c}--;
            .take for recursing( $c ).map({ $head, |$_ });
            $n_count{$c}++;
        }
    }

    return sort gather for $n_count.keys -> $head {
        $n_count{$head}--;
        .take for recursing( $head );
        $n_count{$head}++;
    }
}


my @tests =
    ( (1, 17, 8) , ( (1, 8, 17), (17, 8, 1) ) ),
    ( (2,  2, 2) , ( (2, 2,  2),            ) ),

    ( ((1..14).list) , (  ) ),
    ( ((1..15).list) , ( (8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9),
                         (9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8) ) ),
    ( ((1..16).list) , ( (8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16),
                         (16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8) ) ),
    ( ((1..17).list) , ( (16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17),
                         (17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16) ) ),
    ( ((1..18).list) , (  ) ),
    ( ((1..19).list) , (  ) ),
    ( ((1..20).list) , (  ) ),
    ( ((1..21).list) , (  ) ),
    ( ((1..22).list) , (  ) ),
    ( ((1..23).list) , (
        (2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9, 7, 18),
        (9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 7, 18),
        (18, 7, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9),
        (18, 7, 9, 16, 20, 5, 11, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22),
        (18, 7, 9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2),
        (22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 11, 5, 20, 16, 9, 7, 18), ) ),
    ( ((1..24).list) , (  ) ),
    ( ((1..25).list) , (
        (2, 23, 13, 12, 24, 25, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 5, 20, 16, 9, 7, 18),
        (3, 22, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 24, 25, 11, 5, 20, 16, 9, 7, 18),
        (4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 2, 23, 13, 12, 24, 25, 11, 5, 20, 16, 9, 7, 18),
        (8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 22, 3, 1, 24, 25, 11, 5, 20, 16, 9, 7, 18),
        (9, 16, 20, 5, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 25, 24, 12, 13, 23, 2, 7, 18),
        (10, 15, 21, 4, 12, 13, 23, 2, 14, 22, 3, 6, 19, 17, 8, 1, 24, 25, 11, 5, 20, 16, 9, 7, 18),
        (11, 25, 24, 12, 13, 23, 2, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 5, 20, 16, 9, 7, 18),
        (13, 23, 2, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 24, 25, 11, 5, 20, 16, 9, 7, 18),
        (18, 7, 2, 23, 13, 12, 24, 25, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 5, 20, 16, 9),
        (18, 7, 9, 16, 20, 5, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 2, 23, 13, 12, 24, 25, 11),
        (18, 7, 9, 16, 20, 5, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 25, 24, 12, 13, 23, 2),
        (18, 7, 9, 16, 20, 5, 11, 25, 24, 1, 3, 22, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8),
        (18, 7, 9, 16, 20, 5, 11, 25, 24, 1, 8, 17, 19, 6, 3, 22, 14, 2, 23, 13, 12, 4, 21, 15, 10),
        (18, 7, 9, 16, 20, 5, 11, 25, 24, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 3, 22, 14, 2, 23),
        (18, 7, 9, 16, 20, 5, 11, 25, 24, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 22, 3),
        (18, 7, 9, 16, 20, 5, 11, 25, 24, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 13, 23, 2, 14, 22),
        (18, 7, 9, 16, 20, 5, 11, 25, 24, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 2, 23, 13),
        (18, 7, 9, 16, 20, 5, 11, 25, 24, 12, 13, 23, 2, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4),
        (22, 14, 2, 23, 13, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 24, 25, 11, 5, 20, 16, 9, 7, 18),
        (23, 2, 14, 22, 3, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 24, 25, 11, 5, 20, 16, 9, 7, 18), ) ),
;
use Test;
plan 2+@tests;
for @tests.head(2) -> ( @in, @expected ) {
    is-deeply task2_slow(@in), @expected;
}
for @tests -> ( @in, @expected ) {
    is-deeply task2(@in), @expected;
}