A directed graph is called “DAG” if it has no cycles. Given a DAG, find the shortest path from a starting point to a target point.
The input consists of several test cases. Each test case, begins with three integers N, A, B indicating the number of nodes in the graph (indexing from 0 to N-1), the number of the starting point and the number of the target point. ( 0 < N <= 1000, 0 <= A, B < N ) In the second line, there is an integer K representing K edges. In the next K 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 be equal to T. ( 0 <= R, T < n ) When N, A and B all equal to 0, the input ends.
In each test case, please print “Case”, a space, the case number, a colon and a space orderly shown in the sample output. And then print the shortest path. In the shortest path, print a dash between each node. If there are two or more shortest paths, print the one with minimum number order. And If the shortest path does not exist, please print “INVALID”.