In a graph G, contraction of an edge e with endpoints u, v is the replacement of u and v with a single vertex such that edges incident to the new vertex are the edges other than e that were incident with u orv. TheresultinggraphhasonelessedgethanG. AgraphH isaminor ofagraphGifacopyofH can be obtained from G via repeated edge deletion, edge contraction and isolated node deletion. Minors play an important role in graph theory. For example, every non-planar graph contains either the graph K3,3 (i.e., the complete bipartite graph on two sets of three vertices) or the complete graph K5 as a graph minor. Write a program to find a graph minor Kn,m or Kn in an undirected connected simple graph. Input The input consists of several test cases. The first line of each case contains an integers V (3 ≤ V ≤ 12), the number of vertices in the graph, followed by a string in format ‘Kn’ or ‘Kn,m’ (1 ≤ n, m ≤ V ), the graph minor you’re finding. The following V lines contain the adjacency matrix of the graph (‘1’ means directly connected, 0’ means not directly connected). The diagonal elements of the matrix will always be ‘0’, and the element in row i column j is always equal to the element in row j column i. The last test case is followed by a single zero, which should not be processed. Output For each test case, print the case number and the string ‘Found’ or ‘Not found’. Sample Input 5 K2,2 01111 10000 10000 10000 10000 4 K3 0101 1010 0101 1010 4 K2,2 0101 1011 0101 1110 5 K2,2 01001 10001 00011 00101
2/2 11110 5 K4 01011 10110 01011 11101 10110 0 Sample Output Case 1: Not found Case 2: Found Case 3: Found Case 4: Not found Case 5: Found