import java.util.*;

public class Caterpillar {
  public static Scanner in;
  public static int caseNum;
  public static int n;
  public static int e;
  public static Graph g;

  public static void main(String[] args) {
    in = new Scanner(System.in);
    caseNum = 0;

    while ((n = in.nextInt()) != 0) {
      caseNum++;
      g = new Graph(n);
      e = in.nextInt();
      for (int i = 0; i < e; i++) {
        int v = in.nextInt();
        int w = in.nextInt();
        g.add(v,w);
      }
      boolean conn = g.connected();

      if (!conn || e != n-1) {
         System.out.println("Graph " + caseNum + " is not a caterpillar.");
         continue;
      }

      // For each vertex, see if it is a leaf; if so, delete it:
      ArrayList<Integer> deleted = new ArrayList<Integer>();
      for (int i = 1; i <= n; i++) {
        ArrayList<Integer> nbr = g.edge.get(i);
        if (nbr.size() <= 1)
          deleted.add(i);
      }

      // Special case: only one vertex:
      if (n - deleted.size() <= 1)
         System.out.println("Graph " + caseNum + " is a caterpillar.");
      else {
        // Now see if the remaining edges form a simple path
        for (int i = 0; i < deleted.size(); i++)
          g.delete(deleted.get(i));
        if (g.pathLength() == n -deleted.size())
          System.out.println("Graph " + caseNum + " is a caterpillar.");
        else
         System.out.println("Graph " + caseNum + " is not a caterpillar.");
      } 
    }
  }
}

class Graph {
  public ArrayList<ArrayList<Integer>> edge;
  public int n;

  public Graph(int n) {
    this.n = n;
    edge = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i <= n; i++) {
      edge.add(new ArrayList<Integer>());
    }
  }

  public void add(int i, int j) {
    edge.get(i).add(j);
    edge.get(j).add(i);
  }

  public boolean connected() {
    int count = 0;
    int v = 1;
    boolean visited[] = new boolean[n+1];
    for (int i = 1; i <= n; i++)
      visited[i] = false;
    
    dfs(1,visited);
    for (int i = 1; i <= n; i++)
      if (!visited[i]) return false;
    return true;
  }

  public void delete(int v) {
    for (int i = 1; i <= n; i++) {
      ArrayList<Integer> nbr = edge.get(i);
      int k = nbr.indexOf(v);
      if (k >= 0)
        nbr.remove(k);
    }
    edge.set(v, new ArrayList<Integer>());
  }

  public int pathLength() {
    // Find a vertex of degree 1:
    int i = 1;
    ArrayList<Integer> nbr = null;
    while(true) {
      if (i > n) break;
      nbr = edge.get(i);
      if (nbr.size() == 1) break;
      i++;
    }
    int count = 1;
    boolean visited[] = new boolean[n+1];
    for (int k = 0; k <= n; k++)
      visited[k] = false;
    visited[i] = true;
    while (nbr.size() >= 1) {
      int first = nbr.get(0);
      if (!visited[first]) {
        nbr = edge.get(first);
        visited[first] = true;
      }
      else if (nbr.size() >1) {
        int second = nbr.get(1);
        if (!visited[second]) {
          nbr = edge.get(second);
        visited[second] = true;
        }
      }
      else break;
      count++;
    }
    return count;
  }

  public void dfs(int v, boolean[] visited) {
    ArrayList<Integer> nbr = edge.get(v);
    visited[v] = true;
    for (int i = 0; i < nbr.size(); i++) {
      int w = nbr.get(i);
      if (!visited[w])
         dfs(w,visited);
    }
  }
}