Normalise my decision map

Write a function or program that processes a block of text and returns the new text. Smallest valid program wins.

Each line in the block of text will have the following format:

12:34,56


The first number is the line ID, the other two comma separated numbers are references to other lines.

In the input text the numbers can be any integer greater than or equal to 0. All numbers will be in ASCII encoded decimal with no leading zeros. There will be no duplicate line IDs. There will be no references to non-existent line IDs, although there may be line IDs that are not referenced.

In the output text the lowest numbered line will be moved to the start of the text block and renumbered to 0. Any references to this line must be updated too. The first reference on that line must be 0 or 1. The second reference can only be 2 if the first reference is 1. Otherwise it must be 0 or 1.

All the lines must be in ascending, incrementing order (no skipped numbers). You can only have a reference to line n if there has been a previous reference to line n-1 or the current line ID is n. There must be no lines that are not referenced by lower line IDs except for line 0. Any such lines must be removed before the final output.

You may assume that the input text is always in the correct format.

Test input #1:

45:73,24
78:24,78
89:24,73
73:45,3
72:3,24
3:24,24
24:3,89


Reordered:

3:24,24
24:3,89
89:24,73
73:45,3
45:73,24
78:24,78
72:3,24


Renumbered:

0:1,1
1:0,2
2:1,3
3:4,0
4:3,1
78:1,78
72:0,1


Unreferenced lines removed for final output:

0:1,1
1:0,2
2:1,3
3:4,0
4:3,1


Of course, your program doesn't have to follow this order, just produce the correct output. The output must be a single block of text or the closest equivalent in your language, i.e. no character by character direct output. You may either return it (preferred) or output the whole block directly. Assume your output will be passed to another function or program.

Test input #2

5:2,3
7:3,2
2:4,2
4:2,3
3:4,3


Output:

0:1,0
1:0,2
2:1,2


Test input #3

7:6,3
3:9,7
9:7,3
2:9,6
6:6,7


Output:

0:1,2
1:3,4
2:2,3
3:2,4
4:1,3


def f(s):