2975：Find a Minor

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 or v . The resulting graph has one less edge than G . A graph H is a minor of a graph G if a copy of H 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.

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.

For each test case, print the case number and the string ``Found" or ``Not found".