Necklace

A necklace in an undirected graph is a sequence of cycles C1, C2, . . . , Ck (k ≥ 1), satisfying the conditions below:

1. Any two cycles have no edges in common.
2. There is exactly one common vertex between two adjacent cycles Ci and Ci+1 (1 ≤ i < k) 3. Any two non-adjacent cycles are vertex disjoint, i.e. no vertices in common. Note that any vertex appears in a cycle at most once. A necklace between two vertices S and T is a necklace C1, C2, . . . , Ck such that S belongs to C1 and T belongs to Ck. Given an undirected graph and two vertices S and T, you need find whether a necklace between S and T exists. Input The input consists of multiple test cases. Each test case starts with a line containing two integers N (2 ≤ N ≤ 10, 000) and M (1 ≤ M ≤ 100, 000), which are the number of vertices and the number of edges in the undirected graph, respectively. Each of the following M lines contains two integers A and B (1 ≤ A ̸= B ≤ N), which indicates an undirected edge between vertices A and B. Vertices are numbered from 1 to N. The last line of each test case contains two integers S and T (1 ≤ S ̸= T ≤ N). The last test case is followed by a line containing two zeros. Output For each test case, print a line containing the test case number (beginning with 1) followed by ‘YES’, if the required necklace exists, otherwise ‘NO’. Sample Input 33 12 23 31 13 45 12 23 13 34 34 14 45 12 12

2/2 23 34 34 14 00 Sample Output Case 1: YES Case 2: YES Case 3: NO