#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int N=109;
int box[N],kk;
struct node
{
    int next,t;
}e[N<<5];
int n,m,fa[N];
int in[N];
int father(int now)
{
    if(fa[now]==now) return now;
    else return fa[now]=father(fa[now]);
}
void add(int s,int t)
{
    e[kk].t=t;e[kk].next=box[s];box[s]=kk++;
}
bool dfs(int r,int fa)
{
    int num=0,mark;
    for(int i=box[r];~i;i=e[i].next)
    if(e[i].t!=fa)
    {
        int t=e[i].t;
        if(in[t]==1) continue;
        num++;
        mark=t;
    }
    if(num==0) return 1;
    if(num>=2) return 0;
    return dfs(mark,r);
}
bool init()
{
    scanf("%d",&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    bool wrong=0;
    memset(box,-1,sizeof(box));kk=0;
    memset(in,0,sizeof(in));
    while(m--)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        if(s==t) continue;
        in[s]++;
        in[t]++;
        add(s,t);
        add(t,s);
        int fs=father(s);
        int ft=father(t);
        if(fs==ft) wrong=1;
        fa[fs]=ft;
    }
    for(int i=2;i<=n;i++)
    if(father(i)!=father(1)) wrong=1;
    if(wrong) return 0;
    for(int i=1;i<=n;i++)
    if(dfs(i,0))
    {
        return 1;
    }
    return 0;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int cnt=0;
    while(scanf("%d",&n),n)
    {
        printf("Graph %d is %sa caterpillar.\n",++cnt,init()?"":"not ");
    }
}