트리인가?

면접 대비

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

요약

0 0 쌍이 나올 때까지 방향 간선을 읽고, 주어진 세 조건에 따라 그래프가 트리인지 판정해 케이스 번호와 결과를 출력한다.

문제

트리는 매우 잘 알려진 자료 구조이다. 어떤 자료 구조가 트리가 되려면, 비어 있거나(노드의 개수가 $0$ 개), 노드가 $1$ 개 이상이면서 방향 간선을 가지고 다음 조건을 모두 만족해야 한다.

노드 $u$ 에서 노드 $v$ 로 향하는 간선이 있을 때, 이 간선을 $u$ 의 입장에서는 '나가는 간선', $v$ 의 입장에서는 '들어오는 간선'이라고 하자.

예를 들어, 어떤 방향 그래프는 위 조건을 모두 만족하여 트리가 되고, 어떤 방향 그래프는 조건을 위반하여 트리가 아니다.

간선들의 정보가 주어질 때, 각 그래프가 트리인지 판별하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스는 여러 개의 정수쌍으로 이루어지며, 각 정수쌍 $u$ , $v$ 는 노드 $u$ 에서 노드 $v$ 로 향하는 간선이 존재함을 의미한다. 여기서 $u$ 와 $v$ 는 모두 $0$ 보다 크다. 각 테스트 케이스의 끝에는 두 개의 $0$ 이 주어진다.

모든 입력의 끝에는 두 개의 음의 정수가 주어진다.

각 테스트 케이스마다, 케이스 번호를 $k$ 라고 할 때( $k$ 는 $1$ 부터 시작하여 $1$ 씩 증가한다) 그래프가 트리이면 Case k is a tree.를, 트리가 아니면 Case k is not a tree.를 출력한다.

예제 1

입력

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1

예상 출력

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.