애벌레 그래프

시간 제한1초메모리 제한128 MB

요약

노드가 최대 100개인 무방향 그래프가 주어질 때, 연결된 트리이면서 모든 노드가 하나의 경로 위에 있거나 그 경로에 인접한지 판별한다.

난이도: 보통10점 중 5점
유형: 그래프, DFS, 트리, 구현
정답자: 아직 제출이 없습니다

문제

무방향 그래프가 다음 세 조건을 모두 만족하면 애벌레(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.

를 출력한다.

예제1

예제 1

입력

22
21
1 2 2 3 2 4 2 5 2 6 6 7 6 10 10 8 9 10 10 12 11 12 12 13 12 17
18 17 15 17 15 14 16 15 17 20 20 21 20 22 20 19
16
15
1 2 2 3 5 2 4 2 2 6 6 7 6 8 6 9 9 10 10 12 10 11 10 14 10 13 13 16 13 15
0

예상 출력

Graph 1 is not a caterpillar.
Graph 2 is a caterpillar.