#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int E, V;
int G[100][100];
int degree[100];
int used[100];
int C;
bool able;
int visited;
void dfs(int v, int pre){
    used[v] = 0;
    visited ++;
    for(int i = 0; i < V; i ++){
        if(i != v && i != pre){
            if(G[v][i] == 1 && used[i] == 0){
                able = false;
                break;
            }
        }
    }
    if(!able){
        return;
    }
    for(int i =0; i <V; i ++){
        if(G[v][i] && used[i] == 1){
            dfs(i, v);
            break;
        }
    }
}
int main(){
    int c = 0;
    while(true){
        scanf("%d", &V);
        if(V == 0){
            break;
        }
        scanf("%d", &E);
        int a, b;
        memset(G, 0, sizeof(G));
        memset(degree, 0, sizeof(degree));
        for(int i =0; i < E; i ++){
            scanf("%d %d", &a, &b);
            G[a - 1][b - 1] = 1;
            G[b - 1][a - 1] = 1;
            degree[a - 1] ++;
            degree[b - 1] ++;
        }
        memset(used, -1, sizeof(used));
        C = 0;
        able = true;
        for(int i = 0; i < V; i ++){
            if(degree[i] > 1){
                used[i] = 1;
                C ++;
            }
            if(degree[i] == 0){
                able = false;
            }
        }
        visited = 0;
        for(int i = 0; i < V; i ++){
            if(used[i] == 1){
                dfs(i, -1);
                break;
            }
        }
        if(able && visited == C){
            printf("Graph %d is a caterpillar.\n",  ++c);
        } else {
            printf("Graph %d is not a caterpillar.\n", ++c);
        }
    }
}