Anyone who goes to a psychiatrist ought to have his head examined. Samuel Goldwyn Take any directed graph D with n vertices and m edges. You can make the Lying graph E of B in the following way. E will have m vertices, one for each edge of D. For example, if D has an edge uv, then E will have a vertex called uv. Now, whenever D has edges uv and vw, E will have an edge from vertex uv to vertex vw. There are no other edges in E. You will be given a graph E and will have to determine whether it is possible for E to be the Lying graph of some directed graph D. Input The first line of input gives the number of cases, N (N < 220). N test cases follow. Each one starts with two lines containing m (0 ≤ m ≤ 300) and k. The next k lines will each contain a pair of vertices, x and y, meaning that there is an edge from x to y in E. The vertices are numbered from 0 to m − 1 Output For each test case, output one line containing ‘Case #x:’ followed by either ‘Yes’ or ‘No’, depending on whether E is a valid Lying graph or not. Note that D is allowed to have duplicate edges and self-edges. Sample Input 4 2 1 01 5 0 4 3 01 21 23 3 9 01 02 12 10 20 21 00 11 22
2/2 Sample Output Case #1: Yes Case #2: Yes Case #3: No Case #4: Yes