use Tree ();

my %nodes;

while (<>) {
   my ($child, $parent) = split /:/;

   my $parent_node = $nodes{$parent} ||= Tree->new($parent);
   my $child_node  = $nodes{$child}  ||= Tree->new($child);

   $parent_node->add_child($child_node);
}

my @roots = grep { $_->is_root } values %nodes;

die("Invalid data: No roots\n")
   unless @roots;

foreach (@roots) {
   ...
}