Are trees? P45106


Statement
 

pdf   zip

thehtml

A graph is a set of vertices (also called nodes) and a set of edges among the vertices. A tree is a connex graph without cycles. (A general tree is not more than a tree for which a node has been fixed as root, and where the children of each node are sorted from the left to the right.

(To see an instance with the first graph of the input-output instance, consult the pdf or ps version of this wording.)

Write a program that decides if various given graphs are trees or not. For comfort, we will suppose that the n vertices of a graph are numbered 0, 1, …, n − 1 .

Input

Input starts with the description of various graphs. n lines follow, each one with the number of neighbours of the vertex i-th followed by these neighbours in any order. In all the graphs there is not repeated edges nor edges from a vertex to itself.

Output

For each given graph, your program must print a line that indicates if it is a tree or not.

Public test cases

  • Input

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

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

2
0
0

    Output

    is a tree
is NOT a tree
is NOT a tree
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python