#include <iostream>
#include <stack>
using namespace std;

int n, Adj[101][101], Visited[101], degree[101];
bool IsCat;
stack<int> nStack;

void Init(){
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      Adj[i][j]=0;
  for(int i=1;i<=n;i++)
    degree[i]=Visited[i]=0; 
  IsCat=true;  
}

void GetEdges(){
  int e,a,b;
  cin>>e;
  for(int i=0;i<e;i++){
    cin>>a>>b;
    Adj[a][b]=Adj[b][a]=1;
    degree[a]++;
    degree[b]++;
  }
  Adj[0][1]=Adj[1][0]=1;  //add dummy edge to start traversal
}

void Traverse(int parent){
  int current = nStack.top();
  for(int i=1;i<=n;i++){
    if(Adj[current][i] && i!=parent)
      if(Visited[i]){  //loop found
        IsCat=false;
        return;
      }
      else
      {
        Visited[i]=1;
        nStack.push(i);
        Traverse(current);
      }
  }
}

void checkSpline(){ 
  //first see if connected
  for(int i=1;i<=n;i++)
    if(!Visited[i]){ IsCat=false; return;}
  // check every node if connected to at most 2 non-leaves
  for(int i=1;i<=n;i++){
    int count=0;
    for(int e=1;e<=n;e++)
      if(e!=i && Adj[e][i] && degree[e]>1) count++;
    if(count>2){ IsCat=false; return;}
  }
}

int main() {
  int g=0;
cin>>n;
while(n>0) {
//zero out adj matrix and Visited array
Init();
g++;

// read in edges
GetEdges();

Visited[1]=1;
nStack.push(1);
Traverse(0);

if (IsCat)
  checkSpline();

if(IsCat)
  cout<<"Graph "<<g<<" is a caterpillar."<<endl;
else
  cout<<"Graph "<<g<<" is not a caterpillar."<<endl;

cin>>n;
}

return 0;
}