Mine is playing a game with Tatsumi, where one person sketches some branches and knots and the other determines whether the sketch is of a tree or not. After playing this for a few hours, they've gotten bored and have decided to make the game more abstract. Now, instead of drawing pictures of trees, the couple fills in a ~4 \times 4~ adjacency matrix with either
Their adjacency matrix stores the relationship between any two knots ~u~ and ~v~. Specifically, if ~adj[u][v] = 1~, then there is a branch connecting ~u \to v~. Since branches are undirected, a branch from ~u \to v~ implies a branch from ~v \to u~. In this way, the adjacency matrix is symmetrical in that ~adj[u][v] = adj[v][u]~.
An adjacency matrix representing a tree has exactly one path between any pair of ~u~ and ~v~, and hence has 1 fewer branches than it has knots. Any less and the tree would be disconnected (a forest), and any more and a cycle would exist.
You've decided to join in the fun. Given a ~4 \times 4~ adjacency matrix, can you determine whether it represents a tree or not?
An adjacency matrix, represented by 4 lines, each containing 4 space-separated integers, either
Yes if the given adjacency matrix represents a tree, or
If you are unfamiliar with the definition of a tree, this Wikipedia article might help.
Sample Input 1
0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0
Sample Output 1
Sample Input 2
0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0
Sample Output 2
Explanation of Output for Sample Input 2
Between Sample 1 and Sample 2, there is a difference of one branch: ~0 \longleftrightarrow 1~. This branch creates a cycle, and therefore the number of knots is the same as the number of branches. Hence, it is not a tree.