A directed graph is called “DAG” if it has no cycles. Given a DAG, find the longest path from a starting point to a target point.
The input consists of several test cases. Each test case begins with two integers A, B in a line, indicating the number of the starting point and the number of the target point. ( 0 <= A, B < 100000 ) In the second line, there is an integer N representing N edges. ( 0 < N < 1000 ) In the next N lines, there are two integers R, T in each line which means there is a directed edge from node R to node T and R is not equal to T. ( 0 <= R, T < 100000 ) When A and B both equal to 0, input ends.
In each test case, print “Case”, a space, the case number, a colon and a space orderly shown in the sample output. And then print the length of the longest path. If the longest path does not exist, please print “INVALID”.