트리는 공집합이거나 혹은 하나 이상의 노드로 노드 사이에는 방향성이 있고 연결된 다음 특정을 가진다.

• 루트 노드는 오직 하나이고
• 루트 노드를 제외한 모든 노드는 그 것을 가리키는 하나의 에지를 가진다.
• 루트에서 각 노드로는 방향성을 가지는 에지의 유일한 나열이다.

예를 들어 , 아래 그림에서 노드는 원으로 에지(edge)는 방향을 가지는 선으로 표현한다. 처음 두 개는 트리이고 하나는 트리가 아니다.

에지로 연결된 노드의 집합이 주어질 때 이 구조가 트리인지 아닌지를 알아내는 것이 문제이다.

입력

노드의 번호는 0 보다 큰 정수이다.

출력

• 트리이면 "tree"
• 아니면 "not a tree"

입출력 예

입력

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

출력

tree

입력

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

출력

tree

입력

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

출력

not a tree

출처: North Central North America 1997