Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 0.5 Seconds Memory Limit: 65536K

Total Runs: 513 Accepted Runs: 219

An undirected graph is called a *caterpillar* if it is connected, has no cycles, and there is a path in the
graph where every node is either on this path or a neighbor of a node on the path. This path is called
the *spine* of the caterpillar and the spine may not be unique. You are simply going to check graphs to
see if they are caterpillars.
### Input

### Output

### Sample Input

### Sample Output

For example, the left graph below is not a caterpillar, but the right graph is. One possible spine is shown by dots.

There will be multiple test cases. Each test case starts with a line containing *n* indicating the number
of nodes, numbered 1 through *n* (a value of *n* = 0 indicates end-of-input). The next line will contain an
integer *e* indicating the number of edges. Starting on the following line will be *e* pairs *n*_{1} *n*_{2} indicating
an undirected edge between nodes *n*_{1} and *n*_{2}. This information may span multiple lines. You may
assume that *n* ≤ 100 and *e* ≤ 300. Do not assume that the graphs in the test cases are connected or acyclic.

For each test case generate one line of output. This line should either be

Graphgis a caterpillar.

or

Graphgis not a caterpillar.

as appropriate, where *g* is the number of the graph, starting at 1.

22 21 1 2 2 3 2 4 2 5 2 6 6 7 6 10 10 8 9 10 10 12 11 12 12 13 12 17 18 17 15 17 15 14 16 15 17 20 20 21 20 22 20 19 16 15 1 2 2 3 5 2 4 2 2 6 6 7 6 8 6 9 9 10 10 12 10 11 10 14 10 13 13 16 13 15 0

Graph 1 is not a caterpillar. Graph 2 is a caterpillar.

Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop