Shortest path length:3
1-2-45-6
1-3-45-6
1-3-5-6
1-3-8-6
1-31-8-6
1-3-9-6