#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#include<string>

#include<map>

#include<stack>

#include<vector>

#include<algorithm>

#include<cmath>

#define rep(i,a,b) for(int i = a; i < b; i++)

#define _rep(i,a,b) for(int i = a; i <= b; i++)

using namespace std;

int G[][];

int n, m;

int deg[], vis[];

int main(){

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

    int kase = ;

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

        memset(G,,sizeof(G));

        memset(deg,,sizeof(deg));

        memset(vis,,sizeof(vis));

        scanf("%d", &m);

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

            int u, v;

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

            G[u][v] = G[v][u] = ;

            deg[u]++;

            deg[v]++;

        }

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

            if(deg[i] == ){ //把度为1的点全部删除， 把链上的分叉的消去

                vis[i] = ;

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

                    if(G[i][j])

                        deg[j]--;

                }

            }

        }

        int ok = , _1 = , _2 = ,cnt = ;

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

            if(!vis[i]){

                cnt++;

                if(deg[i] == ) _1++;//统计剩下点度为1的

                else if(deg[i] == ) _2++;//统计剩下度为2的

            }

        }

        if(!(_1 ==  && _2 == (cnt-))) ok = ;//如果有2个度为1， 其他都是2， 那么就是一条链， 其他情况都不符合

        if(ok)

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

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

    }

    return ;

}