#!/usr/bin/perl

use strict;
use warnings;

my %node;

while (<DATA>) {
    my ( $c, $p ) = split;
    if ( $c eq $p ) {  # these are easy, so finish them first
        print;
        next;
    }

    if ( exists( $node{$c}{child_of} )) {
        warn "$.: bad record: $c is child of both $p and $node{$c}{child_of}\n";
        next;
    }
    $node{$c}{child_of} = $p;
    $node{$p}{parent_of}{$c} = undef;
}

# begin the sorted output by looping over values that do not have parents:

for my $parent ( grep { !exists( $node{$_}{child_of} ) } keys %node ) {
    my $children = $node{$parent}{parent_of};  # ref to hash of child values
    trace_down( $children, \%node );
}

sub trace_down
{
    my ( $kids, $tree ) = @_;
    for my $kid ( keys %$kids ) {
        print "$kid $$tree{$kid}{child_of}\n";
        if ( exists( $$tree{$kid}{parent_of} )) {
            trace_down( $$tree{$kid}{parent_of}, $tree );
        }
    }
}

__DATA__
n1 n2
n3 n2
n4 n1
n5 n5
n6 n4
n7 n7
n8 n9
n10 n2
n11 n6
n2 n12
n7 n6
n8 n4