# -*- mode: cperl6; -*-

# 2011 Perl 6 Coding Contest
# Edgar Gonzàlez i Pellicer

use v6;

use LinkedLists;
use Multiset;
use Partition;


# Tree
class Tree {

  # Children
  has @.children;


  # Walk along a tree
  method walk() {
    # Recurse
    my Int $pos = 1;

    # Gather
    my @result = gather {
      self.walk-rec($pos);
    }

    # Remove the last one, unless there is only one
    @result.pop unless @result == 1;

    # Return
    return @result;
  }


  # Walk along a tree
  # Recursive version
  method walk-rec(Int $start is rw) {
    # Our number is...
    my Int $ours = $start++;
    take $ours;

    # Any children?
    for @.children -> $child {
      # Call for each children
      $child.walk-rec($start);

      # Back to where we were
      take $ours;
    }
  }
}


# Rooted trees
my @rooted-trees;
@rooted-trees[0] = [];
@rooted-trees[1] = [ Tree.new ];


# Combine subtrees
sub combine-subtrees(Array $parts, Int $i, Array $cur, Array $result) {
  # End?
  if $i == $parts.elems {
    # Add it
    $result.push(Tree.new(children => $cur.list));
  }
  else {
    # How many of which cardinality
    my $cardinality = $parts[$i].key;
    my $how-many    = $parts[$i].value;

    # Find all subtree multisets
    my @msets = multisets(rooted-trees($cardinality), $how-many);

    # For each one
    for @msets -> $mset {
      # Add it
      my $len = $mset.elems;
      $cur.push(|$mset);

      # Recurse
      combine-subtrees($parts, $i + 1, $cur, $result);

      # Remove it
      $cur.pop for ^$len;
    }
  }
}


# Join two subtrees
sub join-two-subtrees(Array $trees, Array $result) {
  # Loop
  for $trees.keys -> $i {
    for $i ..^ $trees.elems -> $j {
      # Join one to the other (i.e., add one as children)
      my @children = $trees[$i].children;
      @children.push($trees[$j]);
      $result.push(Tree.new(children => @children));
    }
  }
}


# Rooted trees
sub rooted-trees(Int $n) {
  # Generate them
  for @rooted-trees.elems .. $n -> $i {
    # Trees i
    my $trees-i = [];

    # Find the partitions of $n - 1
    for int-partitions($i - 1) -> $part {
      # Combine subtrees
      combine-subtrees($part.uniq-c, 0, [], $trees-i);
    }

    # Set it
    @rooted-trees[$i] = $trees-i;
  }

  # Return them
  return @rooted-trees[$n].list;
}


# We use Jordan's Theorem, as in:
#
#   Roberto ARINGHIERI, Pierre HANSEN, Federico MALUCELLI
#   Chemical Trees Enumeration Algorithms
#   4OR: A Quarterly Journal of Operations Research, 1(1), 67--83, 2003
#
# but lifting the maximum degree restriction

# Unrooted-trees
sub unrooted-trees(Int $n) {
  # Cases
  given $n {

    # Negative or zero
    when * .. 0 {
      # Nothing
      return;
    }

    # One
    when 1 {
      # A single tree
      return Tree.new;
    }

    # Otherwise
    default {
      # Result
      my @result;

      # Parity?
      if $n %% 2 {
	# Even

	# Partitions
	my @partitions = int-partitions($n - 1);
	my $start = partitions-below-or-eq(@partitions, $n div 2 - 1);

	# For each case
	for @partitions[$start ..^ @partitions.elems] -> $part {
	  # Skip one- and two-element partitions
	  next if $part.elems <= 2;

	  # Combine subtrees
	  combine-subtrees($part.uniq-c, 0, [], @result);
	}

	# Join two subtrees
	join-two-subtrees(rooted-trees($n div 2), @result);
      }
      else {
	# Odd

	# Partitions
	my @partitions = int-partitions($n - 1);
	my $start = partitions-below-or-eq(@partitions, $n div 2);

	# For each case
	for @partitions[$start ..^ @partitions.elems] -> $part {
	  # Skip one-element partitions
	  next if $part.elems == 1;

	  # Combine subtrees
	  combine-subtrees($part.uniq-c, 0, [], @result);
	}
      }

      # Return them
      return @result;
    }
  }
}


# Main
sub MAIN(Str $n-str) {
  # Number
  my Int $n = $n-str.Int;

  # Find the trees
  for unrooted-trees($n) -> $tree {
    say($tree.walk.join('-'));
  }
}


# Call main
# @maybe This should be done automatically?
MAIN(|@*ARGS);