Caterpillar

Time limit1sMemory limit128 MB

Summary

Given up to 100 nodes, decide whether the graph is a connected tree whose every node lies on or adjacent to some single path.

Level: Medium5 of 10
Topics: Graph, DFS, Tree, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

Example 1

Input

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

Expected output

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