Thanks to the Interstate Highway System, it is now possible to travel from coast to coast without seeing anything. Charles Kuralt The problem is simple: there are n planets in the galaxy that have human settlements on them. Each planet has a hyperspace jump gate that allows a space ship to teleport from some planet U to some planet V. For technical reasons, not all of the n (n − 1) jumps are allowed. What is the smallest number of jumps that are required to reach planet T from planet S? Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with two lines containing n (1 ≤ n ≤ 100,000) and k (0 ≤ k ≤ 41,000). The next k lines will each be of the form U V1-V2 meaning that the jumps from planet U to planets V 1 through V 2 (inclusive) are forbidden. Finally, the last line will contain S and T . Vertices are numbered from 0 to n − 1. The number of different forbidden pairs will be no larger than 5,000,000. Output For each test case, output one line containing ‘Case #x:’ followed by either the minimum number of jumps, or ‘Impossible’. Sample Input 4 3 1 0 2-2 02 3 1 0 1-2 02 4 4 0 0-3 1 0-3 2 0-3 3 0-3 00 100000 3 0 1-99998 99999 1-50000
2/2 99999 50002-99999 01 Sample Output Case #1: 2 Case #2: Impossible Case #3: 0 Case #4: 3