#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 111

 struct Edge{

     int v,next;

 }edge[MAXN*MAXN];

 int n,m,NE;

 int head[MAXN];

 void Insert(int u,int v)

 {

     edge[NE].v=v;

     edge[NE].next=head[u];

     head[u]=NE++;

 }

 int parent[MAXN];

 void Initiate()

 {

     for(int i=;i<=n;i++){

         parent[i]=i;

     }

 }

 int Find(int x)

 {

     if(x==parent[x]){

         return parent[x];

     }

     parent[x]=Find(parent[x]);

     return parent[x];

 }

 bool Judge()

 {

     int cnt=;

     for(int i=;i<=n;i++){

         if(parent[Find(i)]==i)cnt++;

     }

     return cnt==;

 }

 int dep[MAXN];

 int path[MAXN];

 bool mark[MAXN],vis[MAXN];

 void dfs_dep(int u,int father)

 {

     for(int i=head[u];i!=-;i=edge[i].next){

         int v=edge[i].v;

         if(v==father)continue;

         dep[v]=dep[u]+;

         path[v]=u;

         dfs_dep(v,u);

     }

 }

 bool dfs(int u)

 {

     vis[u]=true;

     for(int i=head[u];i!=-;i=edge[i].next){

         int v=edge[i].v;

         if(vis[v])continue;

         if(mark[u]||mark[v]){

             if(dfs(v))return true;

         }

         return false;

     }

     return true;

 }

 int main()

 {

  //   freopen("1.txt","r",stdin);

     int u,v,st,ed,tmp,t=;

     while(~scanf("%d",&n)&&n){

         scanf("%d",&m);

         NE=;

         memset(head,-,sizeof(head));

         Initiate();

         bool flag=true;

         while(m--){

             scanf("%d %d",&u,&v);

             Insert(u,v);

             Insert(v,u);

             if(Find(u)!=Find(v))parent[Find(u)]=Find(v);

             else flag=false;

         }

         if(!flag||!Judge()){

             printf("Graph %d is not a caterpillar.\n",t++);

             continue;

         }

         dep[]=;

         dfs_dep(,-);

         ed=;

         for(int i=;i<=n;i++){

             if(dep[i]>dep[ed])ed=i;

         }

         dep[st=ed]=;

         dfs_dep(st,-);

         ed=;

         for(int i=;i<=n;i++){

             if(dep[i]>dep[ed])ed=i;

         }

         memset(mark,false,sizeof(mark));

         path[st]=-;

         mark[st]=true;

         tmp=ed;

         while(path[tmp]!=-){

             mark[tmp]=true;

             tmp=path[tmp];

         }

         memset(vis,false,sizeof(vis));

         if(dfs()){

             printf("Graph %d is a caterpillar.\n",t++);

         }else

             printf("Graph %d is not a caterpillar.\n",t++);

     }

     return ;

 }