Minimum Spanning Tree

$G$ is a connected, weighted, undirected graph. A spanning tree $T$ of $G$ is a subgraph that (1) is a tree and (2) connects all vertices of $G$. The weight of a spanning tree is the sum of the weights of its edges. A minimum spanning tree is a spanning tree whose weight is less than or equal to the weight of every other spanning tree.

Write a program that determines whether a given tree $T$ is a minimum spanning tree of a given graph $G$.

The input consists of one or more test cases. Each test case gives a graph $G$ and one or more trees to test.

The first line of a test case contains a single integer $n$ ($1 < n \le 1000$), the number of vertices of $G$. Vertices are numbered from $1$ to $n$.

The next $n-1$ lines give the upper triangle of the weighted adjacency matrix:

W(1,2) W(1,3) ... W(1,n-1) W(1,n)
W(2,3) W(2,4) ... W(2,n)
...
W(n-1,n)

where $W_{i,j}$ ($0 \le W_{i,j} \le 1000$) is the weight of the edge between vertices $i$ and $j$, and $W_{i,j} = 0$ means there is no edge between them.

After the matrix, a line contains a single integer $Q$ ($0 < Q \le 1000$), the number of trees to test on this graph.

Each of the next $Q$ trees is either a single vertex, given by its number, or is written as

(R T1 T2 ... Tc)

where $R$ is the root vertex and $T_1, \dots, T_c$ ($0 < c \le 1000$) are its subtrees, described recursively in the same way.

The end of the input is a line containing a single $0$ in place of $n$.

For each tree, print one line of the form

a.b result

where $a$ is the test case number (starting at $1$), $b$ is the tree number within that test case (starting at $1$), and result is YES if the tree is a minimum spanning tree of $G$ and NO otherwise. Put a single space between $b$ and result, and leave no trailing spaces.