use strict;
use POSIX qw(floor);
use Data::Dumper;

# rank_to_prufer(r, n)
# Generates the Prufer sequence for the n-vertex tree of rank
#  r.
sub rank_to_prufer
{
  my ($rank, $n) = @_;
  my @prufer     = ();

  for(my $i = $n - 2; $i > 0; $i--) {
    my   $new = $rank % $n + 1;
    unshift @prufer, $new;
    $rank = POSIX::floor(($rank - $new + 1) / $n);
  }

  return @prufer;
}

# prufer_to_tree(seq)
# Generates the tree corresponding to the Prufer sequence seq
sub prufer_to_tree
{
  my @prufer  = @_;
  my $n       = scalar @prufer + 2;
  my @edges   = ();
  my @degrees = (1) x $n;

  push @prufer, 1;

  for (0 .. $n - 3) {
    my $i = $prufer[$_] - 1;
    $degrees[$i]++;
  }

  for (0 .. $n - 2) {
    my $x = $n-1;
    while($degrees[$x] != 1) {$x--;}
    my $y = $prufer[$_] - 1;
    $degrees[$x]--;
    $degrees[$y]--;
    my @edge = ($x+1, $y+1);
    push @edges, \@edge;
  }

  return @edges;
}

# example call -- generate a random 6-vertex tree
my @tree = &prufer_to_tree(&rank_to_prufer(rand(1296), 6));