Shell Programming and Scripting

I have a file with two columns of numbers (member IDs):

1 1
2 1
3 1
4 2
5 4
6 1
7 5
8 3
9 2

Think of column 1 as the referee and column 2 as the referrer.

Is there a good way to backtrack who referred who? I would like an output, for this example here to be:

1 1
2 1
3 1
4 2 1
5 4 2 1
6 1
7 5 4 2 1
8 3 1
9 2 1

Does that make sense?

I assume there is a clever way to use join to solve this, but I've been struggling to come up with a solution.

Thanks, in advance, for your help!

Assuming that 'someone' will always be a self referal (1 1), someone is only referred by one other, and will only appear in the left column once, then this will work:

Code:

awk '
    function printchain( who )
    {
        printf( "%s ", who );
        if( a[who] )
            printchain( a[who] );
    }

    {
        order[++oidx] = $1;
        a[$1] =  $1 == $2 ? 0 : $2;
    }

    END {
        for( i = 1; i <= oidx; i++ )
        {
            printchain( order[i] );
            printf( "\n" );
        }
    }
' input-file

perfect. thank you.