Caterpillar

An undirected graph is called a caterpillar if it is connected, has no cycles, and contains a path such that every node is either on this path or adjacent to a node on the path. Such a path is called the spine of the caterpillar, and the spine need not be unique. Your task is to check graphs to determine whether they are caterpillars.

There are multiple test cases. Each test case starts with a line containing $n$, the number of nodes, numbered $1$ through $n$ (a value of $n = 0$ indicates end-of-input). The next line contains an integer $e$, the number of edges. The following lines contain $e$ pairs of node numbers, each pair n1 n2 indicating an undirected edge between nodes n1 and n2; this list may span multiple lines. You may assume that $n \le 100$ and $e \le 300$. Do not assume that the graphs are connected or acyclic.

For each test case, produce one line of output. For the $g$-th graph (numbering from $1$), print

Graph g is a caterpillar.

if the graph is a caterpillar, or

Graph g is not a caterpillar.

otherwise.