#include <cstdio>
#include <iostream>
#include <set>
using namespace std;

typedef set<int> SI;

// A set of integers for each node. Look up std::set for API documentation.
SI nodes[110];

// The type of each node: 0 = unknown, 1 = fuzz, 2 = spine.
int marks[110];

// Count the unknown nodes adjacent to the specified node
int countadj(int n) {
    int count = 0;
    for (SI::iterator it = nodes[n].begin(); it != nodes[n].end(); ++it) {
	if (marks[*it] == 0) ++count;
    }
    return count;
}

int main(void) {
  
  for (int casei = 1; ; ++casei) {
    
    // Clear the adjancency information and marks 
    for (int i = 0; i < 100; ++i) {
      nodes[i].clear();
      marks[i] = 0;
    }
    
    int nnodes; cin >> nnodes;
    if (nnodes == 0) break;
    
    int nedges; cin >> nedges;
    for (int i = 0; i < nedges; ++i) {
      int f, t; cin >> f >> t;
      // Decrementing the node numbers so that nodes are 0..(nnodes-1)
      f -= 1; t -= 1;
      
      // Add the forward and reverse edges to the graph
      nodes[f].insert(t);
      nodes[t].insert(f);
    }
    
    // Set all nodes with only one neighbor to fuzz
    for (int i = 0; i < nnodes; ++i) {
      if (nodes[i].size() <= 1) marks[i] = 1;
    }

    // Find an end of the spine...

    // curr will be the non-fuzz node with minimum adjacent non-fuzz nodes.
    // If no non-fuzz node exists, it will be node 0.
    int curr = 0;
    for (int i = 0; i < nnodes; ++i) {
      // If node i is non-fuzz
      if (marks[i] == 0) {
	// If node curr is fuzz or
	if (marks[curr] != 0 ||
	    // non-fuzz adjacency of i is less than that of curr
	    countadj(i) < countadj(curr)) {
	  curr = i;
	}
      }
    }
	
    bool result = true;
    
    // Walk down the spine starting from curr, marking each node as we go.
    while (result) {
      // Mark curr as a spine node.
      marks[curr] = 2;
      
      int prev = -1;
      int next = -1;
      for (SI::iterator it = nodes[curr].begin(); it != nodes[curr].end(); ++it) {
	if (marks[*it] == 0) {
	  // Found an unknown neighbor. There may be zero, one or more
	  // unknown neighbors: zero means that we stop walking, one
	  // means that we walk to that node, and more mean that we
	  // have encountered a branch.
	  if (next == -1) next = *it;
	  else { result = false; }
	}
	else if (marks[*it] == 2) {
	  // Found a spine neighbor. There may be zero, one or more
	  // spline neighbors: zero means we are on the first spine
	  // node, one means we came from that node, and more mean
	  // that we have encountered a cycle.
	  if (prev == -1) prev = *it;
	  else { result = false; }
	}
      }
      
      // If there are no unknown nighbors, we have nowhere to walk. Stop.
      if (next == -1) break;
      else curr = next;
    }
    
    // Now need to ensure that every node is either on the spine or
    // adjacent to the spine.
    for (int i = 0; result && i < nnodes; ++i) {
      bool safe = marks[i] == 2; // true if i is a spine node
      for (SI::iterator it = nodes[i].begin(); it != nodes[i].end(); ++it) {
	safe |= marks[*it] == 2; // set true if i is adjacent to a spine node
      }
      // All nodes must be safe for the graph to be a caterpillar.
      result &= safe;
    }
    
    printf("Graph %d is ", casei);
    if (!result) printf("not ");
    printf("a caterpillar.\n");
  }
  return 0;
}