This is the model solution Label each vertex by the number from 0 to 99, that is equal to the length of the longest directed path that ends in this vertex. Then every edge goes from a vertex with a smaller label to a vertex with a larger label. Now colour this edge in red if the digit of tens in the larger label is greater than the digit of tens in the smaller label. Otherwise colour this edge in blue. Since the number of tens is the same in all vertices on a blue path, the length of the path cannot exceed 9. Since the number of tens is different in all vertices on a red path, the length of the path also cannot exceed 9.