Stage           Node   Route so far
     1               a      a
     1.1             1      a -> 1
     1.1.1           1      a -> 1 -> 2
     1.1.1.1         5      a -> 1 -> 2 -> 5
     1.1.1.1.1       8      a -> 1 -> 2 -> 5 -> 8
     1.1.1.1.1.1     b      a -> 1 -> 2 -> 5 -> 8 -> b
     1.1.2           4      a -> 1 -> 4
     1.1.2.1         5      a -> 1 -> 4 -> 5
     1.1.2.1.1       8      a -> 1 -> 4 -> 5 -> 8
     1.1.2.1.1.1     b      a -> 1 -> 4 -> 5 -> 8 ->b
     1.2             3      a -> 3
     1.2.1           4      a -> 3 -> 4
     1.2.1.1         5      a -> 3 -> 4 -> 5
     1.2.1.1.1       8      a -> 3 -> 4 -> 5 -> 8
     1.2.1.1.1.1     b      a -> 3 -> 4 -> 5 -> 8 ->b
     1.2.2           7      a -> 3 -> 7
     1.2.2.1         b      a -> 3 -> 7 -> b
     1.2.2.2         8      a -> 3 -> 7 -> 8
     1.2.2.2.1       b      a -> 3 -> 7 -> 8 -> b
     1.3             6      a -> 6
     1.3.1           7      a -> 6 -> 7
     1.3.1.1         b      a -> 6 -> 7 -> b
     1.3.1.2         8      a -> 6 -> 7 -> 8
     1.3.1.2.1       b      a -> 6 -> 7 -> 8 -> b
     1.3.2           9      a -> 6 -> 9
     1.3.2.1         b      a -> 6 -> 9 -> b