In your post (OP) you specify that all numbers other than "-1" are "unique" - but what exactly do you mean? Do you mean that

1. each number appears only once on the left side of (x, y)?
2. do you mean that there is a unique path to each number except -1? That is, if we find $h{2}{6}{4} we will never find a sequence of pairs such that $h{7}{11}{6}{4}.

The two statements are quite different. Unless you are absolutely certain a priori that (2) is true, your algorithm is going to need to check for multiple paths to each number. Then you will have to decide whether those multiple paths are an error or not. Assuming that multiple paths to each number are an error, your code will need to keep track of each path found to each number.

I posted code below to illustrate the point, mainly as a contrast to BrowserUk's elegant solution. I do so with reservations. Bloodnok is right - it is considered bad form on Perl Monks to post a question without at least trying to show your own efforts. But BrowserUK is right too - the OP has posted a difficult problem. We aren't trying to be mean when we say do it yourself: it is just that we are donating our time so others can learn. Trying to solve the problem on your own is essential to really understanding the solution. For further discussion of the point, see The path to mastery.

use strict;
use warnings;
use YAML;

my $hIn= {
(4,-1),
(2,6),
(6,4),
(3,5),
(5,-1),
(99,-1),
};

my $hOut = {};

#keep track of the one and only path to each number
#except -1.
my %hPaths;

while (my ($k,$v) = each(%$hIn)) {

  # have we already found the path to $v
  # and if so do we have more than one path?
  my $aPath = $hPaths{$v};
  if ($aPath) {
    #value was already found - either warn about two paths
    #or patch its path so it starts with the key
    unless ($#$aPath == 0) {
      die "More than one path to <$v>: <@$aPath> and <$k $v>";
    }

    $hPaths{$v} = [ $k, @$aPath];
    $aPath = $hPaths{$k};
    if (!$aPath) {
      $hPaths{$k} = [ $k ];
    } elsif ($#$aPath != 0) {
      die "More than one path to <$k>: <@$aPath> and <$k>";
    }

    $hOut->{$k} = {$v => $hOut->{$v}};
    delete $hOut->{$v};
    next;
  }

  #find the path to $k
  $aPath = $hPaths{$k};
  $hPaths{$k} = $aPath = [ $k ] unless $aPath;

  #follow path to hash for key $k
  my $hNode=$hOut;
  my $i=0;
  $hNode=$hNode->{$aPath->[$i++]} while $i< $#$aPath;

  #add pair to hash
  if ($v == -1) {
    $hNode->{$k} = $v;
  } else {
    $hNode->{$k} = {$v=>{}};
    $hPaths{$v} = [ @$aPath, $v ];
  }
}

# a prettier dumper
print YAML::Dump($hOut);
[download]

Best, beth

Update: added my agreement with BrowserUk's observation about difficulty below.