Given an undirected graph with n nodes rooted at node 1. In this graph for each node we've to find the number of predecessors in the shortest path from the root to this node. Any ideas?

let's say the graph is like this

                 1
                / \
               2   4
               \  /
                3

Here for node 3 predecessors are 2 and 4