题目描述

无向图若满足以下条件则称为毛虫图（$caterpillar$）：
$1$. 连通且无环（即本身是树）。
$2$. 存在一条路径（称为主干），使得所有节点要么在该路径上，要么是该路径上某节点的邻居。
主干可能不唯一，只需存在至少一条即可。

例如，左图不是毛虫图，右图是毛虫图（其中一条主干用圆点标出）。

输入格式

输入包含多个测试用例。每个测试用例：
$1$. 第一行是节点数 ( n )（( 1 \leq n \leq 100 )，( n=0 ) 表示输入结束）。
2. 第二行是边数 ( e )（( 0 \leq e \leq 300 )）。
$3$. 后续 ( e ) 行或多行，每行包含若干整数对 ( n_1 \ n_2 )，表示无向边（节点编号为 ( 1 ) 到 ( n )）。

注意：输入的图可能不连通或包含环，需先判断是否为树（连通且 ( e = n-1 )），再判断是否为毛虫图。

输出格式

对每个测试用例，输出一行：
若图是毛虫图，输出 $Graph g is a caterpillar.$，其中 ( g ) 是测试用例编号（从 $1$ 开始）。
否则，输出 $Graph g is not a caterpillar.$。

输入示例 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  

输出示例 1

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

来源

East Central North America $2006$