//* Problem  : 2561 - Caterpillar
//* Contest  : acm.tju.edu.cn
//* Origin   : East Central 2006
//* Type     : Solution
//* Date     : 2007.08.22
//* Author   : alt
//* Language : C++
//* Compiler : Microsoft Visual C++ 6.0
//* Algoritm : O(n)

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

struct vertex{
	int adj;
	int invalid;
	int link;
	int d;
} a[101];

int n, m;

int solve()
{
	if (n != m + 1) return 0;
	int i, c1 = 0;
	for (i = 1; i <= n; i++)
		if (a[i].adj == 1)
		{
			a[a[i].link].d++;
			a[i].invalid = 1;
		}
	for (i = 1; i <= n; i++)
		if (!a[i].invalid)
		{
			a[i].adj -= a[i].d;
			if (a[i].adj == 1)  c1++;
				else if (a[i].adj > 2) return 0;
		}
	if (c1 != 2 && c1 != 0) return 0;
	return 1;
}

int main()
{
	int i, t1, t2, it = 0;
	while (scanf("%d", &n) == 1 && n)
	{
		memset(a, 0, sizeof(a));
		scanf("%d", &m);
		for (i = 0; i < m; i++)
		{
			scanf("%d %d", &t1, &t2);
			a[t1].adj++; a[t1].link = t2;
			a[t2].adj++; a[t2].link = t1;
		}
		if (solve()) printf("Graph %d is a caterpillar.\n", ++it);
			else printf("Graph %d is not a caterpillar.\n", ++it);
	}
	return 0;
}