애벌레 그래프

무방향 그래프가 다음 세 조건을 모두 만족하면 애벌레(caterpillar) 그래프라고 한다. 연결되어 있고, 사이클이 없으며, 모든 정점이 어떤 경로 위에 있거나 그 경로 위의 정점과 인접해 있는 그런 경로가 존재한다. 이 경로를 애벌레의 척추(spine)라고 하며, 척추는 유일하지 않을 수 있다. 주어진 그래프가 애벌레 그래프인지 판별하면 된다.

여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정점의 개수 $n$이 적힌 줄로 시작하며, 정점은 $1$번부터 $n$번까지 번호가 매겨진다($n = 0$은 입력의 끝을 의미한다). 다음 줄에는 간선의 개수 $e$가 주어진다. 그 다음부터 $e$개의 정점 쌍이 주어지며, 각 쌍 n1 n2는 정점 n1과 n2를 잇는 무방향 간선을 의미한다. 이 목록은 여러 줄에 걸쳐 있을 수 있다. $n \le 100$, $e \le 300$이라고 가정해도 된다. 그래프가 연결되어 있거나 사이클이 없다고 가정해서는 안 된다.

각 테스트 케이스마다 한 줄을 출력한다. $g$번째 그래프($1$번부터 시작)에 대해, 그래프가 애벌레이면

Graph g is a caterpillar.

를, 그렇지 않으면

Graph g is not a caterpillar.

를 출력한다.