use v6;

#returns a list of all forests with depth <= $dm $n nodes, trees which are
#before ($d,$nmax,$max)
#returns all forests of depth <= $n
multi forests(Int $n, 0, Int $nmax = $n, $max = Inf) {[],}
multi forests(Int $n, 1, Int $nmax = $n, $max = Inf) {[[] xx $n],}
multi forests(Int $n, Int $d, Int $nmax where {$n < $nmax}, $max = Inf) {forests($n,$d)}
multi forests(Int $n, Int $d, Int $nmax = $n, $max = Inf) {
		return forests($n,$d-1) if $nmax < $d;
		gather {
			for trees($nmax,$d) Z 1..$max -> $tree, $index {
				for forests($n-$nmax,$d,$nmax,$index) -> $forest {
					take [$tree, @$forest];
				}
			}
			take forests($n,$d,$nmax-1);
		}
}

#returns all trees of depth $n
multi trees(1, 1) {[],}
multi trees(Int $n, 1) {()}
multi trees(Int $n, 2) {[[] xx ($n-1)],}
multi trees(Int $n, Int $d, Int $nmax, $max = Inf, $dmax = $d) {
	($dmax > $d or $nmax > $n) and return trees($n,$d);
	gather {
		for trees($n,$d) Z 1..$max -> $tree,$i{
			take $tree;
		}
	}
}
multi trees(Int $n, Int $d) {
	gather {
		for $d..$n -> $cn {
			for trees($cn-1,$d-1) Z 1..* -> $tree,$index {
				for forests($n-$cn,$d-1,$cn-1,$index) -> $forest {
					take [$tree,@$forest];
				}
			}
		}
	}
}
sub even_trees(Int $n) {
	my $maxd = $n div 2;
	for 2..$maxd -> $cd {
		for ceiling($n/2)..($n-$cd) -> $cn {
			for trees($cn, $cd) Z 1..* -> $t1, $max {
				for trees($n-$cn, $cd,$cn,$max,$cd) -> $t2 {
					say represent([$t1,@$t2]);
				}
			}
		}
	}

}
sub odd_trees(Int $n) {
	my $maxd = ($n-1) div 2;
	for 1..$maxd -> $cd {
		for $cd..($n-1-$cd) -> $cn {
			for trees($cn, $cd) Z 1..* -> $t1, $max {
				for $cd..($cn,($n-1-$cn)).min -> $dn {
					for trees($dn, $cd,$cn,$max) Z 1..* -> $t2, $max2 {
						for forests($n-$cn-$dn-1,$cd,$n-$cn-$dn-1,$max2) -> $w {
							say represent([$t1,$t2,@$w]);
						}
					}
				}
			}
		}
	}
}
multi represent($tree) {
	my $rep = represent($tree,1)[0];
	$rep ~~ s/\-\d+$//;
	return $rep;
}
multi represent($tree,Int $n) {
	return $n,$n+1 if $tree.elems == 0;
	my $c = $n+1;
	my $rep = "$n";
	for @$tree -> $subtree {
		my ($r,$s) = represent($subtree,$c);
		$c=$s;
		$rep ~= "-$r-$n";
	}
	return $rep,$c;
}
multi MAIN(1) {say "1"}
multi MAIN(2) {say "1-2"}
multi MAIN(Int $n) {
	even_trees($n);
	odd_trees($n);
}