Baobab
Problem
An undirected, unweighted graph is given. You need to determine if it is a tree.
Input: The first line contains one natural number N (N ≤ 100) - the number of vertices in the graph. Next, in N lines, N numbers each - the adjacency matrix of the graph: in the i-th line, the j-th position is 1 if vertices i and j are connected by an edge, and 0 if there is no edge between them. There are zeros on the main diagonal of the matrix. The matrix is symmetrical about the main diagonal.
Output: Print "YES" if the graph is a tree and "NO" otherwise.
Examples
# |
Input |
Output |
1 |
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
|
NO |
2 |
3
0 1 0
1 0 1
0 1 0
|
YES |