For each node, find the cycle it reaches using Floyd's algorithm or DFS. Mark all cycle nodes with a flag.
This tells you which nodes are in the cycle. For tail nodes, compute the distance to the cycle by following edges until you reach a cycle node. Count steps as you go. Store whether each node is in a cycle, and if not, how far it is from the cycle. This takes time. You visit each node at most twice.