From G to H and back

“All right, I’m stumped... and I think I’m supposed to be.” Dana Scully There is a funny transformation that you can do with a graph. We start with an undirected graph, G, and build a new graph, H. G has n vertices and m edges. For each edge in G, we create a vertex in H. Two vertices in H are connected by an edge if and only if their corresponding edges in G share a vertex. H will have m vertices and p edges. That’s easy. But what about reconstructing G, given H? Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with two lines containing m (at most 320) and p. p lines follow, each containing two different vertices (numbered from 1 to m) in H which are connected by an edge. Output For each test case, output one line containing ‘Case #x:’ followed by either ‘yes’ or ‘no’, depending on whether there exists some graph G that produces the given graph H. Sample Input 2 3 3 12 23 31 4 3 12 13 14 Sample Output Case #1: yes Case #2: no